Как писать быстрые программы

[Yadryara]

wrest в сообщении #1724252 писал(а):

Я воспринимаю это как "эталонную программу".

Торопитесь. Это ещё только подготовительная стадия. Я так подробно расписываю чтобы у меня в мозгах получше устаканилось и чтобы вам объяснить как собираются 192 делителя.

До боевой проверки пока не добрались.

Вот самые трудные 24 числа из 540 чисел в 45 цепочках:

                                                            Time ms
   Ц  М         О   П   Т     Зн. факт.    ВФ     Д   fint(,4)   numdiv

  33. 4.        1   2   0      19 23 29     6   192      27059    27335
  15. 4.        1   2   0      18 23 29     6   192      21619    21804
  43. 2.        2   1   1         34 34     6   192      17052    17174
  11. 4.        1   2   1         20 47     6   192      15442    15622
  34. 3.        1   3   0      20 21 27     7   192      14687    14885
   8. 2.        2   1   1         32 34     6   192      13975    14145
  37. 8.        2   2   1         29 39     7   192      13888    14001
  36. 8.        2   2   1         29 38     7   192      13437    13576
  34. 2.        2   1   1         20 47     6   192      13301    13368
  16.11.        2   2   1         27 40     7   192      13149    13278
  43. 4.        1   2   1         22 45     6   192      13015    13160
  17. 3.        1   3   0      19 21 28     7   192      12642    12788
  13. 4.        1   2   1         18 48     6   192      12141    12311
  33. 2.        2   1   1         21 46     6   192      11979    12117
   2. 1.        2   2   0      19 21 28     7   192      11861    12000
  35. 8.        2   2   1         22 44     7   192      11785    11953
  31. 5.        1   3   1         18 48     7   192      11750    11826
  29.11.        2   2   1         26 41     7   192      11170    11309
  23. 2.        2   1   1         24 42     6   192      10874    11058
  43.11.        2   2   1         19 48     7   192      10369    10477
  14. 8.        2   2   1         23 43     7   192      10259    10392
  29.10.        2   2   1         19 48     7   192      10125    10285
  44. 6.        2   1   1         29 37     6   192       9995    10132
  45. 3.        1   3   1         25 40     7   192       9923    10099

fint(,4) — factorint(chislo, 4)
numdiv   — numdiv   (chislo)

[Yadryara]

Факторизовать надо то самое частное, которое получается после нескольких первых фильтраций. Давайте на примере самой сложной цепочки.

   Ц  М         О   П   Т     Зн. факт.    ВФ     Д   fint(,4)   numdiv
  33. 4.        1   2   0      19 23 29     6   192      27059    27335

Идём слева направо.

Ц = 33. — 33-я цепочка в списке из 45. Вот её значение n:

68266317661664606327183333781435813609832740288225653290206720707881056245

4. — номер места в этой цепочке. То есть самое трудное число на 3 больше чем n:

68266317661664606327183333781435813609832740288225653290206720707881056248

О = 1 — В болванку поставлено 1 обязательное простое не больше 11.
П = 2 — В болванку поставлено 2 произвольных простых больше 11, но не больше 137. Болванка стала паттерном.
Т = 0 — Число 68266... не разделилось ни на одно предпростое больше 137, но не больше 2^20-2.

Значит частное равно 68266... делённое на 1 обязательное простое и на 2 произвольных простых. И вот это частное должно дать 8 делителей, самая вероятная сборка — из трёх различных простых факторов в первой степени, то бишь — pqr.

Снова смотрим в таблицу, ещё правее:
Да, действительно, три фактора были найдены: 19-значный, 23-значный и 29-значный. 192 делителя собрались на этом месте.

Таким образом, важна скорость именно факторизации частного, а не всего числа 68266...

Допустим, у нас есть время факторизации всех частных для всех 45 цепочек. Вот его пока и примем за эталон.

Допустим, мы каким-то образом вовремя бросили факторизацию некоторых чисел. И нашли не 45 цепочек, а половину — 23. И если время работы программы, которое для больших чисел сильно зависит от времени факторизации частных, стало вдвое меньше, то итоговая скорость нахождения цепочек не изменилась. А вот если мы нашли половину цепочек за втрое меньшее время, то да, это прогресс.

[Yadryara]

Значит, следующий этап — получение этих самых частных. Их меньше чем чисел в 45 цепочках (которые имеют вид n+mes-1) — из 540 где-то 400 с чем-то.

wrest, сможете самостоятельно их получить?

[wrest]

Yadryara в сообщении #1724266 писал(а):

сможете самостоятельно их получить?

Вы сначала запостили 270 чисел, post1723976.html#p1723976
затем 66 чисел post1724164.html#p1724164
и вот теперь

Yadryara в сообщении #1724253 писал(а):

Вот самые трудные 24 числа из 540 чисел в 45 цепочках:

Я пожалуй подожду, когда в вашей неделе останется одна пятница

-- добавлено через 2 минуты --

Yadryara в сообщении #1724253 писал(а):

Торопитесь.

Действительно. Буду ждать

-- добавлено через 3 минуты --

Yadryara в сообщении #1724257 писал(а):

А вот если мы нашли половину цепочек за втрое меньшее время, то да, это прогресс.

Ага. А если нашли только 1/10 на за в 20 раз меньшее время? Какой уровень потерь интересует/допустим?
Например, вот числа которые вообще не надо факторизовать, из ваших "66 чисел"

? v=readvec("20_74_povozr_x11.txt");print(#v)
66
? vfac=vector(#v,i,factor(v[i],2^20));
time = 27 ms.
? vquot=vector(#v,i,vfac[i][#vfac[i][,1],1]);
time = 1 ms.
? for(i=1,#v,if(ispseudoprime(vquot[i]),print("Число номер ",i," факторизовалось само")))
Число номер 13 факторизовалось само
Число номер 19 факторизовалось само
Число номер 25 факторизовалось само
Число номер 36 факторизовалось само
Число номер 38 факторизовалось само
Число номер 53 факторизовалось само
time = 6 ms.
?

6 миллисекунд на число.
То есть, если вы готовы потерять 90% чисел, то скорость перебора возрастёт на порядки.

[Yadryara]

wrest в сообщении #1724270 писал(а):

Вы сначала запостили 270 чисел,

Это были именно частные.

Вот всё-таки не зря я старательно расписывал раскадровки. Сейчас уровень понимания вырос. И, если идти от найденных цепочек, то частные для них надо делить на группы, для каждой цепочки — свои частные.

Например, вот есть 4 первые цепочки из 45:

611142354891569765230302686332186116343885992050683915745888694620256245
8270524074670532399671484627515335041989800251815802192673525572636256245
9266186576049688464673021364017844528144851479450172473102652889909856245
12772696442739943221809077341497956726456499563581607373911653396533856245

И для них есть 4 группы частных:

5974048907998229269267127336775803072951243009174921557210289
20654280462363241714926020701657010634912243541893106711857868067
90350781691000713801585735756720896985202332259185715977865030021
4147049256904957421083971325743622199825511590377041934109770741411
135292504635416234203476071607342461644628863998213916417980966193
21428884768869468964189654139431134262177456191033661001733841
408709404340519257853820901473944401947896668122798208615198237823
1967967138068781546089303277567457586964484992676371913075041281039

3572063686106128227522792437170143863410608076937377179835110501347
159042422881245575163868401744458579323676017303484523531278134930123
248402728742611042016404739412779539435922383157712776215124059
65333613167857061827493383692551181194712861654450994116093693529
236550967090746949941065647597076199018292817896599202624580921
11710476565905178619003872038959766431136000356553348237413841518777
166704901711929334171645636288219288679376305409985172118828463577
101848727583253687006446537455240321190948724838872496338524279255163
131608044105575547065888010675094046052337081331714721662917
5531020622424782484609412055333007227983853554151615392164990237823
79705335179166214554722216584562700989539267803179252952690995999

178189042268560602758990449675355650323926992797395724647179971730123
5278092195873552957025094879754356730892918571308849951795639
62877874274263669620765847158255825743342187445376014284665957941411
1316515713128348102232792027528042815329761149339428521086865539497
13120264178477434994227286887104912606222798554973695537136499667129
376521049036822914245673019084550797313537768166503453683279367
177799266560167481477339422903097792005235464721969692092690400067347
81114423726130641756021654732985517697010328721597058846357
49136631075070810338751069156341480217224140621021337251054891161
33884360251036470717177779108909163981295052308157067533697741538807

641303735894670009268024605073833609656130898137860703585695257781
1952315243314570386712060872092257720060489058502770704871129824259
2788767861038341770733609862049114454846619319576209072919422309
3525380382145003575988756879240107218740372432187885784770266171
63905420145670312251460407599977268714876635610027117165197928123
376791628344904283451004956461921620951612111457197729666329659
47816983380153922240411092452689998638857012252226507099295474697
408192240096115633092802499561708041381907209194677855033874989363

Видите, разное количество частных, не более 11-ти. А ведь во всех цепочках количество чисел одинаковое — 12.

wrest в сообщении #1724270 писал(а):

затем 66 чисел post1724164.html#p1724164
и вот теперь

Yadryara в сообщении #1724253 писал(а):

Вот самые трудные 24 числа из 540 чисел в 45 цепочках:

А вы, кстати, поняли, что эти 66 чисел входят в эти 540? То есть я для надежности набрал побольше статистики.

Yadryara в сообщении #1724257 писал(а):

А вот если мы нашли половину цепочек за втрое меньшее время, то да, это прогресс.

Ага. А если нашли только 1/10 на за в 20 раз меньшее время? Какой уровень потерь интересует/допустим?

Фиг знает. Понятно что не меньше одной.

Не забываем, что D(192,15) пока не найдено ни одной.

Вроде неплохая оценка скорости получается, когда находок не меньше сотни. Но, в связи с отсутствием такого количества, считаю, что пока можно ориентироваться на 45 имеющихся цепочек. Может ночью ещё поищу.

Но важный момент. В одном посте больше двух сотен частных и не поместится, тогда поместилось 270, а они были короче. Средняя длина нынешнего частного — 65 знаков. Поэтому я и спросил, сможете ли вы их самостоятельно получить. Чтобы не пересылать частями. Хотя по почте вроде больше прислать могу.

Программу, которая формирует списки именно частных, я уже написал, работает, 4 списка показал здесь же, в этом посте.

wrest в сообщении #1724270 писал(а):

Ага. А если нашли только 1/10 на за в 20 раз меньшее время? Какой уровень потерь интересует/допустим?

Решил ещё раз ответить, исходя из итоговой сотни.

Допустим, я нашёл 1000 цепочек. А вы нашли 1/10, то есть 100 цепочек, за 1/20 от моего времени. Тогда Вы Большой Молодец — 2-кратное ускорение скорости нахождения.

[wrest]

Yadryara в сообщении #1724274 писал(а):

Например, вот есть 4 первые цепочки из 45:

Yadryara в сообщении #1724274 писал(а):

И для них есть 4 группы частных:

Yadryara в сообщении #1724274 писал(а):

Видите, разное количество частных, не более 11-ти.

Ничего не понял.

-- добавлено через 44 секунды --

Yadryara в сообщении #1724274 писал(а):

А вы, кстати, поняли, что эти 66 чисел входят в эти 540?

В какие ещё 540?

-- добавлено через 1 минуту --

Yadryara в сообщении #1724274 писал(а):

Хотя по почте вроде больше прислать могу.

Не надо по почте, всё должно быть в открытом доступе для всех.

[Yadryara]

wrest в сообщении #1724275 писал(а):

Ничего не понял.

Ну как же, я недавно увидел вашу добавку к посту, вы же уже сами заметили, что не все частные надо факторизовать:

wrest в сообщении #1724270 писал(а):

Например, вот числа которые вообще не надо факторизовать, из ваших "66 чисел"

Так и есть.

Именно поэтому для 540 чисел в 45 цепочках частных будет не 540, а 430. 110 — лишние.

wrest в сообщении #1724275 писал(а):

В какие ещё 540?

Я выше приводил простой расчёт. Если длина цепочки 12 чисел, а количество цепочек 45, то простым перемножением получится всего 540 чисел в этих цепочках.

Ну и вот, кстати, 430 частных смогу переслать только за два поста.

[wrest]

Yadryara в сообщении #1724278 писал(а):

Ну и вот, кстати, 430 частных смогу переслать только за два поста.

Вы только не торопитесь, подумайте будут ли они актуальными (для анализа) хотя бы пару недель.
Подумайте также, присылать ли частные, или числа целиком или только первые числа цепочек.
Факторизация по табличным простым делается околомгновенно, за это не переживайте.
Прибавлять по единице чтобы из первого числа цепочки получить остальные я тоже смогу, надеюсь.
И главное - приложите так же и какую-нибудь программу (несекретную и покороче) время работы или другой параметр которой можно было бы взять за единицу для последующего сравнения.

[Yadryara]

wrest в сообщении #1724279 писал(а):

только первые числа цепочек.

Я выше уже показал 45 первых чисел цепочек. Это было сегодня.

И можно не пересылать, да, я уже сделал и отладил программу. Кстати, вот ещё раз внёс исправления. Нужно ведь не просто знать частные, а знать как их надо раскладывать, знать ожидаемое количество делителей — 4 или 8.

То есть вы запишете 45 первых чисел цепочек в файл с тем самым именем. Затем запустите вот эту прогу

(PARI)

default(parisizemax, 128M);

{obobyaz = 0; obproiz = 0; obsvob = 0; kolcha = 0; sumdlcha = 0;
print;

n=readvec("20_74_povozr.txt");


for(nomcep=1, #n,

for(dobmes=0, 11,


t0=getwalltime(); F = factorint(n[nomcep] + dobmes, 4); t1=getwalltime()-t0;


obyaz = 0; proiz = 0; svob = 0; stroka = ""; pro = 1;

print1(nomcep, ". ", dobmes + 1, ".     ");

write1("log3.txt", nomcep, ". ", dobmes + 1, ".     ");


for(j=1, matsize(F)[1],

if( F[j,1] <=  11                    , obyaz++; obobyaz++; pro *= F[j,1]^F[j,2] );

if( F[j,1]  >  11 && F[j,1] <= 137   , proiz++; obproiz++; pro *= F[j,1]^F[j,2] );

if( F[j,1]  > 137 && F[j,1] <= 2^20-2, svob++;  obsvob++;  pro *= F[j,1]^F[j,2] );

if( F[j,1] > 2^20-2,

stroka = concat(stroka, strprintf("%3d", #digits(F[j,1])))));


if( svob <= 1 && matsize(F)[1] >= 6 , cha = ( n[nomcep] + dobmes ) / pro;
kolcha++; sumdlcha += #digits(cha);
t0=getwalltime(); nmdvcha = numdiv(cha); t2=getwalltime()-t0;
write("cha3.txt", cha, , "   ",nmdvcha);
);


print("   ", obyaz, "   ", proiz, "   ", svob, "     ", stroka, "     ", matsize(F)[1], "   ", nmdvcha, "       ", t1, "     ", t2, "       ", kolcha, "       ", sumdlcha\kolcha );

write("log3.txt", "   ", obyaz, "   ", proiz, "   ", svob, "     ", stroka, "     ", matsize(F)[1], "   ", nmdvcha, "       ", t1, "     ", t2, "       ", kolcha, "       ", sumdlcha\kolcha );

);
print;
write("log3.txt",);
write("cha3.txt",);
);

print;print(obobyaz, "   ", obproiz, "   ", obsvob, "       ", kolcha, "       ", sumdlcha/kolcha+.);print;


}quit

и она вам в файл напечатает 430 цепочек, сгруппировав их и указав ожидаемое количество делителей.

Вот для этих первых 4-х чисел:

611142354891569765230302686332186116343885992050683915745888694620256245
8270524074670532399671484627515335041989800251815802192673525572636256245
9266186576049688464673021364017844528144851479450172473102652889909856245
12772696442739943221809077341497956726456499563581607373911653396533856245

Она даёт такие списки частных:

5974048907998229269267127336775803072951243009174921557210289   4
20654280462363241714926020701657010634912243541893106711857868067   4
90350781691000713801585735756720896985202332259185715977865030021   8
4147049256904957421083971325743622199825511590377041934109770741411   8
135292504635416234203476071607342461644628863998213916417980966193   8
21428884768869468964189654139431134262177456191033661001733841   4
408709404340519257853820901473944401947896668122798208615198237823   8
1967967138068781546089303277567457586964484992676371913075041281039   8

3572063686106128227522792437170143863410608076937377179835110501347   8
159042422881245575163868401744458579323676017303484523531278134930123   8
248402728742611042016404739412779539435922383157712776215124059   4
65333613167857061827493383692551181194712861654450994116093693529   4
236550967090746949941065647597076199018292817896599202624580921   4
11710476565905178619003872038959766431136000356553348237413841518777   8
166704901711929334171645636288219288679376305409985172118828463577   8
101848727583253687006446537455240321190948724838872496338524279255163   8
131608044105575547065888010675094046052337081331714721662917   4
5531020622424782484609412055333007227983853554151615392164990237823   8
79705335179166214554722216584562700989539267803179252952690995999   4

178189042268560602758990449675355650323926992797395724647179971730123   8
5278092195873552957025094879754356730892918571308849951795639   4
62877874274263669620765847158255825743342187445376014284665957941411   8
1316515713128348102232792027528042815329761149339428521086865539497   8
13120264178477434994227286887104912606222798554973695537136499667129   8
376521049036822914245673019084550797313537768166503453683279367   4
177799266560167481477339422903097792005235464721969692092690400067347   8
81114423726130641756021654732985517697010328721597058846357   4
49136631075070810338751069156341480217224140621021337251054891161   4
33884360251036470717177779108909163981295052308157067533697741538807   8

641303735894670009268024605073833609656130898137860703585695257781   4
1952315243314570386712060872092257720060489058502770704871129824259   8
2788767861038341770733609862049114454846619319576209072919422309   4
3525380382145003575988756879240107218740372432187885784770266171   4
63905420145670312251460407599977268714876635610027117165197928123   4
376791628344904283451004956461921620951612111457197729666329659   4
47816983380153922240411092452689998638857012252226507099295474697   4
408192240096115633092802499561708041381907209194677855033874989363   4

Ну и в другой лог, а также на экран напечатает немало разнообразной статистики.

[Dmitriy40]

По моему достаточно показывать начальное число цепочки n и её паттерн v[], всё остальное получается из этого легко:
частное: (n+d-1)/v[d] (d - место в цепочке)
ожидаемый numdiv большого числа: 192/numdiv(v[d])
ожидаемый формат большого числа если остались лишь первые степени простых: valuation(192/numdiv(v[d]),2) - количество факторов p, pq, pqr, pqrs, pqrst, ...

И разумеется и все n и все соответствующие им v[] можно положить сразу в один файл в формате [[n,v[]], [n,v[]], [n,v[]], [n,v[]], ...] и проходить по нему циклом.

[wrest]

Dmitriy40 в сообщении #1724295 писал(а):

По моему достаточно показывать начальное число цепочки n и её паттерн v[], всё остальное получается из этого легко:

Я тут придумал хитрый (ну в смысле синтаксиса) кундштюк. Пусть дано n, тогда интересующее нас частное и количество делителей в факторизованной (т.е. без частного) части ищем так без всяких паттернов, например:

? n=30470088979000909073642116609093411675480368362620434836912695687311456245;
? n_r(n)=my(nfac=factor(n,2^20));return([nfac[#nfac[,1],1],numdiv(nfac)/2]);
? print(n_r(n))
[2199859301539708909398494773453579689205021434905489682564034333, 48]
?

[Yadryara]

Dmitriy40 в сообщении #1724295 писал(а):

частное: (n+d-1)/v[d] (d - место в цепочке)

Нет. Вы забыли про 6-ю фильтрацию, по предпростым до 2^20. Нужно делить ещё и на предпростые, если они есть.

[Dmitriy40]

wrest
Тем более, значит хватает и просто n, без всяких этих огромных таблиц частных.

[Yadryara]

wrest, ловко. Знакомое число 3047... А, оно есть в списке из 45 чисел на 18 месте. Проверил, да для этой цепочки частные:

2199859301539708909398494773453579689205021434905489682564034333   4
585940713414886140410794135015834230904203076085928134243157872530123   8
857933231618683807382307126053517861613165662526949635240423772371   4
29733624272794139237405626009861650909515311003209684952739528491   4
6946747141961718320910978914460510629395642476146868472726631   4
426107414261354101270376973332961510257319018328305012542830112537219   8
3027192753997314797381456316002673739223705456823978343612693   4
1000599981673781094026496174161953746053815165407164559610769449   4
179374975574438493496216853934556297840123606261365971105952966437   4

Ну и поправил numdiv(nfac)/2 на 192/numdiv(nfac)*2

[wrest]

Yadryara в сообщении #1724281 писал(а):

и она вам в файл напечатает 430 цепочек, сгруппировав их и указав ожидаемое количество делителей.

Запустил, работало очень долго, что-то печатало, потом сказало "гудбай" и вышло в командную строку, время замерить не удалось. Закончилось так:

45. 1.        2   2   1       7 55     7   4       35     0       420       65
45. 2.        2   1   0       8 18 44     6   8       2094     0       421       65
45. 3.        1   3   1      25 40     7   4       18000     1       422       65
45. 4.        1   2   0      11 29 30     6   8       4067     0       423       65
45. 5.        1   3   1      10 54     7   4       38     0       424       65
45. 6.        2   1   1      22 43     6   4       11704     0       425       65
45. 7.        0   4   1      25 38     7   4       8391     0       426       65
45. 8.        2   2   0       8  9 53     7   8       96     0       427       65
45. 9.        0   4   0       8 11 48     7   8       212     0       428       65
45. 10.        2   2   0       9 28 32     7   8       4135     0       429       65
45. 11.        2   2   0       7 26 37     7   8       10110     0       430       65
45. 12.        2   2   0      66     5   8       0     0       430       65


765   1260   376       430       65.783720930232558139534883720930232558

Goodbye!
~/gp-scripts $