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

[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), а с ним и скорость упала.

[wrest]

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

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

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

? my_ecm(n,7,random(100),7500)
time = 1,083 ms.
%80 = 4996884852786721
? my_ecm(n,7,random(100),7500)
time = 636 ms.
%81 = 4996884852786721
? my_ecm(n,7,random(100),7500)
time = 3,958 ms.
%82 = 4996884852786721
? n
%83 = 324565680788732394698667827438290422220315664174985530827493
?

rounds=7, ну вот и время скачет в 7 раз

[Yadryara]

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

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

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

Имеете в виду что если my_ecm вернёт 0, то нужно будет увеличить b1 и вызвать my_ecm ещё раз?

Да.

Проверил эту идею. Пока получается медленнее:

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

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

ECM 1,1,80       3!3!5!5!**    360   17   1e43       1464       377      1045     336109
ECM 1,1,80-106   3!3!5!5!**    360   17   1e43       1464       405      1125     312354

Но тут важнейший вопрос.

Сейчас пока сделано так:

Вызов функции my_ecm(cha,rounds,seed,b1) первоначально осуществляется с параметрами (cha,1,1,80).
Затем, если фактор не найден, b1 увеличивается на треть и осуществляется повторный вызов с параметрами (cha,1,1,106).

Так во время этого нового вызова проверяются все 106 вариантов, включая те 80, что были проверены только что или именно новые 26 вариантов?? Можно конечно по времени попытаться посмотреть.

[Yadryara]

На всякий случай проверил ещё и дальнейшее увеличение b1 со 106 до 141:

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

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

ECM 1,1,80       3!3!5!5!**    360   17   1e43       1464       377      1045     336109
ECM 1,1,80-106   3!3!5!5!**    360   17   1e43       1464       405      1125     312354
ECM 1,1,80-141   3!3!5!5!**    360   17   1e43       1464       428      1189     295597

Да, время растёт, скорость падает. При этом убедился (печатая результаты после обращения к my_ecm) что хоть и редко, но фактор находится при увеличении b1 с 80 до 106.

И вот ещё таким способом убедился:

b1                                               80     106     141
комплект
  0    9   приход цепочек на 10-ю фильтрацию:   166 --> 164 --> 154
  0   19   приход цепочек на 10-ю фильтрацию:   168 --> 157 --> 152
  0   49   приход цепочек на 10-ю фильтрацию:   163 --> 159 --> 158

Видно что количества цепочек пока неуклонно падают.

Вот поэтому и важно брать факторизацию под контроль. Потому что я пока не понимаю откуда функция my_ecm знает что при новом обращении для того же самого частного, но для другого b1, старые проверки повторно делать уже не надо??

И ведь то же самое небось справедливо и для раундов и для сид. То есть если я укажу что надо считать 3 раунда, а не один, как раньше, то my_ecm посчитает 1-й повторно, и только затем 2-й и 3-й раунды?

Вот поэтому алгоритм Полларда пока хорош. Я же с его помощью могу считать, например, именно те c которые хочу, не пересчитывая по новой.