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

[Yadryara]

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

А Вы уверены что при таких малых B1 у Вас ECM вообще находит делители?

Конечно. Я же смотрю как меняется количество чисел проходящих через фильтрации. Увеличение B1 приводит к заметному уменьшению этого количества.

Ну вот скриншот, кстати:

Rass prime:   0   9

  *** init_Test_11: Warning: increasing stack size to 16000000.
190938930696113892631885832608505261746170                            1111111                7   7
  *** init_Test_11: Warning: increasing stack size to 32000000.
  *** init_Test_11: Warning: increasing stack size to 64000000.
6047536011333786481860506970924606894667770                           1111111                7   7
8420244572402813946685447489259187174782970                     1     1111111                8   7
3173653590174475624877102674720209484670970                           1111111                7   7
6679455272441551993183732976246124087883770                     1     1111111                8   7
7256806239648830738793393335825485143730170                           1111111                7   7
4061271504729413926475453376393002555467770                           1111111   1            8   7
4722521479120038221657981266700202583934970                     1     1111111                8   7
5467670460694008066413376687735241585022970                           1111111                7   7
6026861908813234994159018561219943419467770                           1111111   1            8   7
7845958762264950894269160874981588665010170                  1  1     1111111                9   7
9706142795776225376697333841638971255064570                           1111111                7   7
165901603535455992397325819998460783794170                            1111111                7   7
3561630223173838380913676471174066698622970                           1111111                7   7
9239979957232142009320618949890636197451770                           1111111                7   7
6426234739350138715311530823574307760715770                           1111111                7   7
9363714489040308470912956884305356675147770                           1111111                7   7
4483379927708303873741858453262962009266170                           1111111                7   7
6339303068472661169855568981842268133963770                           1111111                7   7

37,502 ms


[0, 44, 16, 20, 21, 7, 13, 19]     140

Видите, 19 цепочек в этом потоке нашёл. А всего на последнюю фильтрацию пришли 140 цепочек. Это при настройке my_ecm(cha,3,1,90).

0 — с непрерывным куском (слева направо) длиной 0;
44 — с непрерывным куском длиной 1;
16 — с непрерывным куском длиной 2;
...
13 — с непрерывным куском длиной 6;
19 — с непрерывным куском длиной 7, то есть полная цепочка.

Ну так вот, если планомерно уменьшать B1, то есть брать не 90, а 80, 70 и так далее, то на последнюю фильтрацию будет приходить всё больше, 150, 160 ... Даже больше 300 было. При этом количество полных цепочек так и будет 19. Ну может иногда и гульнёт до 18 или до 20. Правда, я пока только 19 видел для этого потока и этого комплекта.

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

И я не понимаю почему у Вас опять флуктуации количества цепочек (найденных ECM делителей) при изменении B1, у меня их нет как выше видно, т.е. Вы измеряете что-то малопонятное, а не скорость ECM.

У меня флуктуации именно что количества полных цепочек. Пока всего лишь на 1%.

Конечно, я измеряю не скорость ECM, а именно что скорость работы всей программы. И показываю именно эту скорость в правом столбце раз за разом, уже много дней.

И это как раз не малопонятное, а самое что ни на есть понятное: программа за 370 секунд нашла 1400+ полных цепочек, что и даёт среднюю скорость более 300 тысяч полных цепочек в сутки.

[Dmitriy40]

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

И это как раз не малопонятное, а самое что ни на есть понятное:

Это понятно в плане скорости работы программы, но малопонятно в плане влияния на неё параметров вызова ECM - ведь в итоге общая скорость зависит не только от параметров вызова ECM, но и от дальнейших фильтраций! И поменяв что-то далее придётся все тесты про ECM проводить заново! Если Вам так хочется по тысяче раз перемерять одно и то же - дело Ваше конечно.

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

О взаимовлиянии seed и B1 (слева B1, слева направо seed 1...100, 1 означает что делитель найден):

? for(b=60,80, print1(b,": ");for(i=1,100, print1(isnull(Z_ECM(1870078940459684045521259474606403291546522792763031595107297821330123,1,i,b))>0)); print)
60: 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
61: 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
62: 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
63: 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
64: 1110000000000000000000000000011111111111111111111111111111111000000000000000000000000000000000000000
65: 1110000000000000000000000000011111111111111111111111111111111000000000000000000000000000000000000000
66: 1110000000000000000000000000011111111111111111111111111111111000000000000000000000000000000000000000
67: 1110000000000000000000000000011111111111111111111111111111111000000000000000000000000000000000000000
68: 1111111111111111111111111000011111111111111111111111111111111000000000000000000000000000000000000000
69: 1111111111111111111111111000011111111111111111111111111111111000000000000000000000000000000000000000
70: 1111111111111111111111111000011111111111111111111111111111111000000000000000000000000000000000000000
71: 1111111111111111111111111000011111111111111111111111111111111000000000000000000000000000000000000000
72: 1111111111111111111111111000011111111111111111111111111111111000000000000000000000000000000000000000
73: 1111111111111111111111111000011111111111111111111111111111111000000000000000000000000000000000000000
74: 1111111111111111111111111000011111111111111111111111111111111000000000000000000000000000000000000000
75: 1111111111111111111111111000011111111111111111111111111111111000000000000000000000000000000000000000
76: 1111111111111111111111111000011111111111111111111111111111111000000000000000000000000000000000000000
77: 1111111111111111111111111000011111111111111111111111111111111000000000000000000000000000000000000000
78: 1111111111111111111111111000011111111111111111111111111111111000000000000000000000000000000000000000
79: 1111111111111111111111111000011111111111111111111111111111111000000000000000000000000000000000000000
80: 1111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000
time = 58,689 ms.

Видно что seed влияет не монотонно, а вот B1 - монотонно.

[wrest]

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

Я же именно это и проверил 100-кратным запуском одинакового варианта - и нет, либо находит все 100 раз, либо все 100 раз не находит делителя,

Ну так стократный запуск с тем же seed -- поэтому и не находит. Seed надо менять :)

[Dmitriy40]

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

Ну так стократный запуск с тем же seed -- поэтому и не находит. Seed надо менять :)

Тоже уже проверил и показал, всё равно не эквивалентно:

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

О взаимовлиянии seed и B1 (слева B1, слева направо seed 1...100, 1 означает что делитель найден):

Если посмотрите на Z_ECM() и ECM_init() в файле ifactor1.c, то увидите что инициализируется ещё много всего кроме seed. Так что даже подобрав ровно те же seed для следующих запусков они всё равно не станут эквивалентными.

[wrest]

Вообще B1 меньшие 100 это дичь какая-то
Там должен трудиться Поллард.
Просто Yadryara использует Полларда, написанного Квеном, а надо бы системный.
Ну с другой стороны, меньше методов -- проще программировать.

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

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

Если посмотрите на Z_ECM() и ECM_init() в файле ifactor1.c, то увидите что инициализируется ещё много всего кроме seed.

Ну так структура создаётся, да. Но всё остальное то детерминированное.

[Dmitriy40]

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

Но всё остальное то детерминированное.

А с чего Вы взяли что содержимое структуры E останется неизменным после вызова ECM_loop()? Если бы осталось, то да, можно было бы заменять f=Z_ECM(n,r,s,b) на for(i=1,r, if(f=Z_ECM(n,1,s,b), break) ). Но оно меняется. А значит вызовы не эквивалентны.

Кстати, оказывается rounds в Z_ECM это вовсе не количество кривых! Кривых в разы больше, оно сидит в E.nbc и вычисляется в ECM_init() как N/2-80, но не менее 8шт, где N длина аргумента в битах. Для 66-значных чисел N=220 и соответственно PARI считает сразу по 30 кривых каждый rounds. Тогда не удивительно что делители находятся даже с rounds=1, реально то кривых десятки.

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

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

Видно что seed влияет не монотонно, а вот B1 - монотонно.

Гипотеза про B1 тоже опровергнута, тоже не монотонно:

(Длинные строки)

? m=vector(170); for(b=10,900, t=[isnull(Z_ECM(1870078940459684045521259474606403291546522792763031595107297821330123,1,s,b))>0 | s<-[1..#m]]; if(t<>m, m=t; print(b,":\t",strjoin(m))); if(vecmin(m)>0, break))
64:     11100000000000000000000000000111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
68:     11111111111111111111111110000111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
72:     11111111111111111111111110000111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111
80:     11111111111111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111
84:     11111111111111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111
152:    11111111111111111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111
164:    11111111111111111111111111111111111111111111111111111111111111111100000000000000000000000111111111111111111111111111111110000000000000000000000000000000001111111111111111
187:    11111111111111111111111111111111111111111111111111111111111111111111111111110000000000000111111111111111111111111111111110000111111111111111111111111111111111111111111111
200:    11111111111111111111111111111111111111111111111111111111111111111111111111110000000000000111111111111111111111111111111110000000000000000000000000000111111111111111111111
372:    11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110000111111111111111111111111111111111111111111111
462:    11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
time = 1h, 8min, 332 ms.

Т.е. с B1=200...371 находит делитель при меньшем количестве разных seed чем с B1=187...199 и B1=372...461.

[wrest]

Dmitriy40
Вот моя статистика
Число то же.
"h:35" -- множитель найден 35 раз из 100
"t:1234" -- функция отработала 100 раз за 1234мс
В качестве seed везде использовано

 B1  |  rounds =1  |  rounds = 3 |  rounds = 5 |  rounds = 7 |
-------------------------------------------------------------
50  |h:0 t:  1350 |h:6  t: 3931 |h:37 t: 5704 |h:72 t: 7091 |
75  |h:54 t: 1752 |h:62 t: 3490 |h:94 t: 3674 |h:99 t: 4536 |
100 |h:65 t: 1989 |h:74 t: 3388 |h:93 t: 4136 |h:98 t: 4423 |
125 |h:55 t: 2426 |h:66 t: 4553 |h:90 t: 5878 |h:100 t: 5661|
150 |h:57 t: 2613 |h:77 t: 5002 |h:91 t: 6023 |h:100 t: 5364|
175 |h:79 t: 2874 |h:87 t: 4811 |h:100 t: 4243|h:100 t: 5937|
200 |h:90 t: 3192 |h:96 t: 3923 |h:100 t: 4677|h:100 t: 4464|
225 |h:86 t: 3321 |h:100 t: 4915|h:100 t: 4101|h:100 t: 4412|
250 |h:79 t: 3718 |h:100 t: 4707|h:100 t: 4220|h:100 t: 4675|
275 |h:80 t: 3955 |h:100 t: 4923|h:100 t: 4247|h:100 t: 4647|
300 |h:86 t: 4040 |h:100 t: 5858|h:100 t: 5530|h:100 t: 5333|
325 |h:87 t: 4145 |h:100 t: 5097|h:100 t: 5832|h:100 t: 5119|
350 |h:87 t: 4403 |h:100 t: 5299|h:100 t: 6239|h:100 t: 5302|
375 |h:100 t: 4261|h:100 t: 4063|h:100 t: 4085|h:100 t: 4256|
400 |h:100 t: 4412|h:100 t: 4386|h:100 t: 4287|h:100 t: 4186|

Видим, что можно увеличивать B1 или rounds, минимальное время то же самое.

Нотчисло неважное, надо с множителем побольше.

[Dmitriy40]

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

В качестве seed везде использовано

И что? Это важно.

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

Видим, что можно увеличивать B1 или rounds, минимальное время то же самое.

Вы тоже видите кучу аномалий в таблице? Увеличение (а тем более уменьшение!) времени от увеличения rounds при h=100.
Вот что при увеличении B1 время скачком падает - это понятно.
Но можно сделать вывод что лучше всего ставить достаточно большое B1 и rounds побольше, а там уж если делитель нашёлся, то будет быстро. Но как-то это нелогичный вывод, ведь если не найдётся, то будет весьма медленно, а таких случаев может быть много. Надо бы проверять не на 100 одинаковых числах, а на реальных данных, как Yadryara делает (только ИМХО без фильтраций после ECM).

Ну и плюс возникает вопрос: а что собственно будем оптимизировать? Понятно что время, вопрос при каких условиях. Требовать ли h=100 или ограничиться скажем h=50 или h=67 или даже h=200/len (типа два делителя на всю цепочку) или h=110/len*(n_pq+2*n_pqr+3*n_pqrs) (чтобы в среднем получалось достаточно делителей на цепочку для срабатывания 1.1шт ispseudoprime).

[wrest]

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

Вы тоже видите кучу аномалий в таблице? Увеличение (а тем более уменьшение!) времени от увеличения rounds при h=100.

Ну это объяснимо вероятностным характером ECM.
При "достаточном большом" B1 увеличение rounds перестаёт увеличивать время, т.к. множитель находится раньше чем заканчивается rounds.

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

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

Но можно сделать вывод что лучше всего ставить достаточно большое B1 и rounds побольше, а там уж если делитель нашёлся, то будет быстро.

Ну я сделал не такой вывод
Надо делать как сделали в pari : увеличивать B1 при rounds=1. Так мы повышаем вероятность за счёт обоих факторов -- делаем несколько заходов ( rounds) И увеличиваем B1, делая и то и другое одновременно.

Вопрос только по какому закону и до каких пределов уаеличивать B1, т.е. когда сдаваться (и переходить к mpqs).

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

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

Ну и плюс возникает вопрос: а что собственно будем оптимизировать?

Ахахах, так это же основной вопрос! Я не знаю. Ждем-с идей от Yadryara или вас.

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

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

Надо бы проверять не на 100 одинаковых числах, а на реальных данных, как Yadryara делает

Так реальные данные (а именно -- распределение минимального множителя) сильно зависят от предыдущих "фильтраций". А от этого распределения (от какой-то характеристики - среднего, медианы или чего-то такого) сильно зависит какой оптимальный B1 брать за стартовый, как быстро повышать и на каком B1 остановиться. А у вас с Yadryara в этом отношении (параметров фильтрации) разные стратегии.

[Dmitriy40]

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

Ну это объяснимо вероятностным характером ECM.

Это было бы объяснимо вероятностным характером ECM если бы в алгоритме ECM использовался случайный seed, а при фиксированном (или даже просто детерминированном) seed ECM не вероятностный. Правда заранее сказать найдёт делитель или нет нельзя, но этот результат (не нашёл или нашёл и какой) не меняется от запуска к запуску, т.е. полностью детерминирован начальными условиями (в том числе seed).
И если для таблицы использовался фиксированный seed, то аномалии непонятны.

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

Вопрос только по какому закону и до каких пределов уаеличивать B1, т.е. когда сдаваться (и переходить к mpqs).

Это решаемо.
Как и порог для factor(n,2^15) подбирали чтобы время работы каждого следующего было раз в 10 больше предыдущего, так и тут можно так же B1 увеличивать. Ну или в 3 раза, учитывая что процент нахождения делителей растёт быстрее линейного. Но разумеется не сразу для каждого места, а только после проверки всех мест, как и с factor.
Предел примерно так же: чтобы общее время ECM не превысило планируемое время MPQS.
Запускать ли вообще MPQS (или любое финальное разложение) и учитывать ли его в тестах скорости - ещё вопрос. Можно и оставлять дырявые кандидаты, сохраняя с одной (или 2-3) дыркой в файл для отдельной медленной допроверки - есть немалый шанс что решение несколько дальше найдётся быстрее чем допроверятся все такие кандидаты. Опять же, скорость генерации таких кандидатов можно и нужно плавно регулировать, чтобы не получился завал.
Это для задачи поиска неизвестной цепочки.
Для задачи поиска миллиона известных цепочек критерии можно чуть пересмотреть, что в общем тоже не проблема.

[Yadryara]

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

Надо бы проверять не на 100 одинаковых числах, а на реальных данных, как Yadryara делает

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

Ахахах, так это же основной вопрос! Я не знаю. Ждем-с идей от Yadryara или вас.

Ну так я же у вас уже неоднократно спрашивал. Вот вы исследовали D(24,6), затем D(48,6), перешли вы оттуда к D(96,6)? Если перешли, то теперь попробуйте перейти к D(192,6). И оттуда уже остаётся лишь один шаг к D(192,7), которую я сейчас исследую.

И будем говорить на одном языке. И на реальных данных.

[Yadryara]

Между тем решил попробовать уменьшить количество итераций и в алгоритме Полларда. Со старых 30 тысяч. Тоже для 8-й фильтрации. И тоже получается заметное ускорение, хотя и не 40-процентное, как в случае с ECM. Но 34-процентное получается.

Это тот самый алгоритм Полларда (Квеновский), что я показывал выше.

6-поточный счёт, серия 1-0-6-0.

Факторизация    Произв.    Обсч.   2^   n от    Найдено     Время   Милсек/   Скорость
8-я фильт.      простые    патт.        0 до    D(192,7)   секунд   паттерн   корт/сут

Pol 1,  2000   3!3!5!5!**    360   17   1e43       1464       404      1121     313459
Pol 1,  2500   3!3!5!5!**    360   17   1e43       1464       400      1109     316726
Pol 1,  3000   3!3!5!5!**    360   17   1e43       1464       398      1105     317886
Pol 1,  3100   3!3!5!5!**    360   17   1e43       1464       402      1117     314670
Pol 1,  3200   3!3!5!5!**    360   17   1e43       1464       387      1074     327005
Pol 1,  3300   3!3!5!5!**    360   17   1e43       1464       400      1108     316995
Pol 1,  3400   3!3!5!5!**    360   17   1e43       1464       393      1090     322360
Pol 1,  5000   3!3!5!5!**    360   17   1e43       1464       408      1132     310429
Pol 1, 10000   3!3!5!5!**    360   17   1e43       1464       412      1143     307274
Pol 1, 20000   3!3!5!5!**    360   17   1e43       1464       482      1336     262969
Pol 1, 30000   3!3!5!5!**    360   17   1e43       1464       522      1449     242526

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

И я не понимаю почему у Вас опять флуктуации количества цепочек

Как понимаю, одной из причин является попытка одновременной записи в лог от нескольких потоков. Иногда происходит сбой нумерации и два, а то и три потока начинают считать один и тот же юнит. Если это урожайный юнит, то происходит перебор нормативного количества, если недород то недобор.

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