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

[wrest]

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

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

Тут надо подбирать опытным путём, какими шагами идти. Встроенная факторизация повышает B1 в 1,21 раза
Но я бы шагал намного шире, например двукратно. И начинал бы не с 80, а с 200.

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

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

Вот поэтому и важно брать факторизацию под контроль.

...

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

Вот поэтому алгоритм Полларда пока хорош.

Ок, удачи с Поллардом :)

[Yadryara]

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

Тут надо подбирать опытным путём, какими шагами идти. Встроенная факторизация повышает B1 в 1,21 раза

Это, кстати, пока несущественно. А существенно: повторяются ли старые вычисления при новом обращении к my_ecm?

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

Но я бы шагал намного шире, например двукратно. И начинал бы не с 80, а с 200.

Но ведь экспериментально установлено, что оптимум пока в районе b1=80.
Когда речь идёт об ускорении реальных программ, неужто всерьёз предлагаете игнорировать эксперимент?

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

Вообще B1 меньшие 100 это дичь какая-то

Это не дичь, это, видать, то самое чудо которым вы интересовались

Обратите внимание, что это для цепочек длиной лишь 7. То есть даже для таких коротких цепочек важно вовремя бросать факторизацию и смотреть другие места. Потому что проверка другого места может быстро дать основание отбросить всю цепочку.

В длинных цепочках мест конечно больше, но числа прям сильно больше. Предполагаю, что и оптимальное значение b1 будет больше.

[Dmitriy40]

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

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

B1 это не варианты.
Если по аналогии, то это праймориал до которого искать цепочки (которые аналог делителей). При этом перебираются не все возможные варианты, а лишь один случайным образом (в зависимости от seed) выбранный список из например rounds*30 штук. И чем B1 больше, тем больше цепочек можно найти, но и тем больше числа и потому медленнее каждая проверка.
Если запускать с теми же seed и B1, то проверяться будут да, те же варианты кривых, потому вызов rounds>a после rounds=a перепроверит часть вариантов. Но если поменять seed или B1, то проверяться будут вообще говоря уже совсем другие варианты даже при том же rounds. Даже если поменять только B1, то всё равно, списки размажутся по большим числам и проверяться будут уже другие варианты даже при том же seed. Можно считать что seed это n0, а B1 это m из формулы n=n0+m*i, где i=1..rounds*30, аналогия ещё грубее, но даёт понять что меняя хоть seed, хоть B1, проверяться будут другие варианты, и что с ростом B1 числа n увеличиваются, а seed на величину чисел (и соответственно скорость работы) практически не влияет.

Проверить всё это можно посмотрев внимательнее на выдачу факторизации после \g 4, там наверняка будут отличия при нахождении делителя при разных B1. Ну вот пример:

? \g 4
   debug = 4
? isnull(Z_ECM(1870078940459684045521259474606403291546522792763031595107297821330123,1,1,80))
ECM: time =      0 ms
ECM: B1 =   80, B2 =   8800,    gss =   32*420
ECM: time =     16 ms, B1 phase done, p = 83, setting up for B2
ECM: time =      0 ms, entering B2 phase, p = 293
time = 16 ms.
%239 = 5761788911
? isnull(Z_ECM(1870078940459684045521259474606403291546522792763031595107297821330123,1,1,100))
ECM: time =      0 ms
ECM: B1 =  100, B2 =  11000,    gss =   32*420
ECM: time =     31 ms, B1 phase done, p = 101, setting up for B2
ECM: time =      0 ms, entering B2 phase, p = 311
time = 31 ms.
%240 = 5761788911

Видите другое значение p в B2 фазе, значит что-то поменялось. Что - непонятно.

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

И да, 31мс вовсе не обязательно вдвое больше 16мс. Потому что это явно округление на тик таймера и реальное время может быть например 18мс и 14мс, или 33мс и 29мс. На самом деле разница и правда небольшая:

? for(i=1,1000, isnull(Z_ECM(1870078940459684045521259474606403291546522792763031595107297821330123,1,1,80)));
time = 23,807 ms.
? for(i=1,1000, isnull(Z_ECM(1870078940459684045521259474606403291546522792763031595107297821330123,1,1,100)));
time = 26,879 ms.

Вот потому и нельзя сравнивать скорости таких быстрых вычислений, слишком груб тик таймера.

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

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

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

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

Можно считать что seed это n0, а B1 это m из формулы n=n0+m*i, где i=1..rounds*30, аналогия ещё грубее, но даёт понять что меняя хоть seed, хоть B1, проверяться будут другие варианты,

Потому я уже тыщу раз говорил что повторные вызовы лучше делать с другим seed, чтобы покрыть больше вариантов кривых. А лучше скорее всего вообще каждый раз случайно выбирать seed. Одинаковые seed важны для многократных тестов скорости, чтобы выполнение было детерминированным от запуска к запуску одинаковых тестов (не вызовов ECM). Но и с random это реализуется стандартным способом через setrand.

[wrest]

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

Обратите внимание, что это для цепочек длиной лишь 7. То есть даже для таких коротких цепочек важно вовремя бросать факторизацию и смотреть другие места. Потому что проверка другого места может быстро дать основание отбросить всю цепочку.

Ну тогда B1 можно повышать не по каждому месту, а в конце цепочки.

[Dmitriy40]

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

Ну тогда B1 можно повышать не по каждому месту, а в конце цепочки.

И это я много раз повторял ... Что лучше сначала проверить всю цепочку с одним B1, потом уже снова всю (недоразложенную) с другим.
А ещё можно B1 иметь разный для каждого места цепочки. Ну если вдруг там будут сильно разные по величине числа (частные). Смысла немного, но и делается легко.

[Yadryara]

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

При этом перебираются не все возможные варианты, а лишь один случайным образом

Раз случайным, значит могут быть совпадения.

И опять это называется "а вы друзья, как ни садитесь". Пока сколько ни менял параметры, наилучший результат по скорости всё равно при одном раунде и одном сиде:

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

Факторизация      Произв.    Обсч.   2^   n от    Найдено     Время   Милсек/   Скорость
8-я фильтрация    простые    патт.        0 до    D(192,7)   секунд   паттерн   корт/сут
ECM 1,1,60       3!3!5!5!**    360   17   1e43       1464       447      1239     283489
ECM 1,1,60-80    3!3!5!5!**    360   17   1e43       1464       417      1157     303611
ECM 1,1,60-106   3!3!5!5!**    360   17   1e43       1464       444      1232     285270

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


Факторизация      Произв.    Обсч.   2^   n от    Найдено     Время   Милсек/   Скорость
8-я фильтрация    простые    патт.        0 до    D(192,7)   секунд   паттерн   корт/сут
ECM 1,1,60       3!3!5!5!**    360   17   1e43       1464       447      1239     283489
ECM 2,1,60       3!3!5!5!**    360   17   1e43       1464       511      1418     247714

b1                                           1,1,60   2,1,60
комплект
  0    9   приход цепочек на 10-ю фильтрацию:   224 ---> 189
  0   19   приход цепочек на 10-ю фильтрацию:   234 ---> 189
  0   49   приход цепочек на 10-ю фильтрацию:   224 ---> 183


Факторизация      Произв.    Обсч.   2^   n от    Найдено     Время   Милсек/   Скорость
8-я фильтрация    простые    патт.        0 до    D(192,7)   секунд   паттерн   корт/сут
ECM 1,1,80       3!3!5!5!**    360   17   1e43       1464       377      1045     336109
ECM 2,1,80       3!3!5!5!**    360   17   1e43       1464       461      1280     274571

b1                                           1,1,80   2,1,80
комплект
  0    9   приход цепочек на 10-ю фильтрацию:   166 ---> 143
  0   19   приход цепочек на 10-ю фильтрацию:   168 ---> 143
  0   49   приход цепочек на 10-ю фильтрацию:   163 ---> 144


Факторизация      Произв.    Обсч.   2^   n от    Найдено     Время   Милсек/   Скорость
8-я фильтрация    простые    патт.        0 до    D(192,7)   секунд   паттерн   корт/сут
ECM 1,1,60       3!3!5!5!**    360   17   1e43       1464       447      1239     283489
ECM 1,2,60       3!3!5!5!**    360   17   1e43       1464       461      1280     274474

b1                                           1,1,60   1,2,60
комплект
  0    9   приход цепочек на 10-ю фильтрацию:   224 ---> 215
  0   19   приход цепочек на 10-ю фильтрацию:   234 ---> 226
  0   49   приход цепочек на 10-ю фильтрацию:   224 ---> 224


Факторизация      Произв.    Обсч.   2^   n от    Найдено     Время   Милсек/   Скорость
8-я фильтрация    простые    патт.        0 до    D(192,7)   секунд   паттерн   корт/сут
ECM 1,1,80       3!3!5!5!**    360   17   1e43       1464       377      1045     336109
ECM 1,2,80       3!3!5!5!**    360   17   1e43       1464       420      1166     301261

b1                                           1,1,80   1,2,80
комплект
  0    9   приход цепочек на 10-ю фильтрацию:   166 ---> 162
  0   19   приход цепочек на 10-ю фильтрацию:   168 ---> 165
  0   49   приход цепочек на 10-ю фильтрацию:   163 ---> 162

[Yadryara]

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

Что лучше сначала проверить всю цепочку с одним B1, потом уже снова всю (недоразложенную) с другим.

Это по сути означает добавление ещё одной фильтрации. Лучше пока проверю уже имеющуюся 9-ю фильтрацию с помощью my_ecm. А потом уже вернусь и к этому варианту с добавлением фильтрации.

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

А ещё можно B1 иметь разный для каждого места цепочки. Ну если вдруг там будут сильно разные по величине числа (частные).

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

Ну вот пример:

#ostmes1 = 4   [7, 5, 3, 6]

1014539125345925379330506609733627359
11035163294240391887991601438359341
486941891826709947586962038033497
321747606235123756660812636192871

То есть имеется 4 частных на местах 3, 5, 6, 7 и для которых необходимое количество делителей равно 4.

А порядок 7, 5, 3, 6 — это уже с учётом величины частных. Ну и сами частные проверяются так: сначала самое большое, то, которое на 7-м месте, затем то которое на 5-м (оно на два порядка меньше), ну и так далее.

Может это и неправильно, так сортировать, хотя я вроде проверял. Дело в том что если быстро находится фактор, то он обычно в пределах 6-11 знаков. Соответственно, оставшееся частное гораздо длиннее и навряд ли простое. А составное — это перебор и выбрасывание всей цепочки.

Сомневаюсь что надо как-то b1 настраивать по месту, хотя возможно и это попробую.

[Dmitriy40]

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

Пока сколько ни менял параметры, наилучший результат по скорости всё равно при одном раунде и одном сиде:

А я из Ваших данных вижу что seed 1->2 уменьшает количество цепочек на выходе, иногда существенно (224->215), что есть хорошо.
Почему при этом падает общая скорость мне неведомо.
Скорость самого ECM от seed зависит очень нетривиальным образом (скорее всего сильно запутано и с исходным числом и с находимым делителем):

? for(s=1,20, t=getwalltime(); for(i=1,100, isnull(Z_ECM(1870078940459684045521259474606403291546522792763031595107297821330123,1,s,600))); print1(getwalltime()-t,"\t"))
3374    3375    3373    3373    3379    3373    3373    3383    3373    3374    3373    3389    3405    3377    8757    8743    8741    8745    8741    8783

Время в мс на сотню ECM.
Видно что seed=1...14 для этого числа и этого делителя (да, делитель здесь всегда один и тот же находится) выполняются одинаково быстро.
Так что нельзя сказать что seed=2 быстрее или медленнее seed=1 на любых данных, это должно сильно зависеть от конкретных данных. И на большой выборке разницы быть не должно. Хотя конечно надо или перепроверить (на реально большой случайной выборке с оценкой достоверности результата) или изучить код PARI.

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

я их сортирую в порядке убывания частных.

Странно, вроде логично в порядке возрастания - чем меньше числа, тем быстрее выполняется факторизация, и ECM тоже, ведь и делители по идее должны быть меньше (в среднем).

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

Сомневаюсь что надо как-то b1 настраивать по месту, хотя возможно и это попробую.

При такой маленькой разнице в порядке чисел - лишнее, да. Было бы хоть порядков 5-7 ...
Скорее важнее будет настраивать B1 в зависимости от формата места (pq, pqr, pqrs), ведь от него зависит размер делителя. Но и это тоже можно очень потом.

[wrest]

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

А ещё можно B1 иметь разный для каждого места цепочки. Ну если вдруг там будут сильно разные по величине числа (частные). Смысла немного, но и делается легко.

Ну тут такое дело. B1 выбирается же по предположению о величине наименьшего множителя.
Для "случайных" чисел, можно например смотреть сюда: https://members.loria.fr/PZimmermann/re ... arams.html

Но у нас числа очень неслучайные, по распределению наименьшего множителя, даже с учётом того, что в них убраны множители до 2^20 (или типа того).

В  pari/gp во встроенной факторизации ведь тоже числа "фильтруются": сперва по таблице до 2^20 (если по умолчанию не установлено другое), затем по пользовательской таблице factor_add_primes, затем Поллард убирает мелкие множители и только потом начинается ECM.

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

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

Скорее важнее будет настраивать B1 в зависимости от формата места (pq, pqr, pqrs), ведь от него зависит размер делителя.

Формат места это что мы хотим там видеть, а не что там на самом деле :)

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

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

Скорость самого ECM от seed зависит очень нетривиальным образом (скорее всего сильно запутано и с исходным числом и с находимым делителем):

Ну так если повезло, то нашлось быстрее и процесс быстро закончился, а если не повезло - то вообще не нашлось, и всё это время считалось. Детерминированность ECM заключается в том что вычисления закончатся не позже гарантированного времени. Но могут и раньше :)

[Dmitriy40]

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

Поллард убирает мелкие множители

Чего-то я сомневаюсь что Поллард ищет делители в порядке возрастания или до некоего порога (т.е. убирает мелкие), это свойство скорее ECM, по моему Поллард находит любые делители, просто чем меньше делитель, тем вероятнее его обнаружить, потому и получается эффект нахождения меньших делителей. По моему в самом алгоритме Полларда нет зависимости от величины делителя, ну насколько я понимаю его математику.
А в PARI (и не только в нём, в YAFU тоже) Поллард вызывается перед ECM из-за своей скорости работы, он сильно проще и потому каждая итерация (то что в ECM называется кривыми или грубо rounds в PARI) быстрее и можно за разумное время сделать их больше и выше вероятность найти хоть какой-то делитель (не меньший, какой получится).

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

Формат места это что мы хотим там видеть, а не что там на самом деле :)

Но ожидаемый размер меньшего делителя (и соответственно B1 в ECM) зависит именно от наших ожиданий (формата места), а не от реальности.

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

Ну так если повезло, то нашлось быстрее и процесс быстро закончился, а если не повезло - то вообще не нашлось, и всё это время считалось.

Для всех seed=1..20 (и даже до 200) в примере выше всегда находился один и тот же делитель, это специально перепроверил.
Кстати время seed=155...186 в полтора раза меньше seed=1...14, 23мс против 33мс. А максимальное время 130мс при seed=77. Для данного конкретного числа (выше) и B1. Делитель находится всегда тот же.
И почти на 100% уверен что для другого числа (и делителя) картина зависимости от seed будет другой.

[Yadryara]

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

А я из Ваших данных вижу что seed 1->2 уменьшает количество цепочек на выходе, иногда существенно (224->215), что есть хорошо.

Хорошо, но это же копейки.

Да, фильтрация улучшается, а скорость уменьшается. Стало быть надо пока делать наоборот.

И действительно: ухудшив 9-ю фильтрацию, за счёт уменьшения количества итераций в алгоритме Полларда в 15 раз, добился увеличения скорости аж на 43%:

6-поточный счёт, серия 1-0-6-0. 8-я фильтрация: ECM 1,1,80 

Факторизация      Произв.    Обсч.   2^   n от    Найдено     Время   Милсек/   Скорость
9-я фильтрация    простые    патт.        0 до    D(192,7)   секунд   паттерн   корт/сут
Pol 1, 30000     3!3!5!5!**    360   17   1e43       1464       377      1045     336109
Pol 1,  2000     3!3!5!5!**    360   17   1e43       1464       262       727     483289
Pol 1,  2500     3!3!5!5!**    360   17   1e43       1464       263       730     481485
Pol 1,  3000     3!3!5!5!**    360   17   1e43       1464       266       737     476826

b1      8-я фильтрация: ECM 1,1,80   9-я: Pol 1,30000   1,3000   1,2500   1,2000
комплект
  0    9   приход цепочек на 10-ю фильтрацию:     166 ---> 275 ---> 295 ---> 313
  0   19   приход цепочек на 10-ю фильтрацию:     168 ---> 276 ---> 290 ---> 306
  0   49   приход цепочек на 10-ю фильтрацию:     163 ---> 287 ---> 302 ---> 314

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

Скорее важнее будет настраивать B1 в зависимости от формата места (pq, pqr, pqrs), ведь от него зависит размер делителя.

Так ведь это же давным-давно делается. 8-я фильтрация делается именно для 4-х делителей, то есть pq, а 9-я — для 8 делителей, то есть pqr.

[Dmitriy40]

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

И действительно: ухудшив 9-ю фильтрацию, за счёт уменьшения количества итераций в алгоритме Полларда в 15 раз, добился увеличения скорости аж на 43%:

Тут не только ухудшение фильтрации (и соответственно замедление последующих стадий) как было с изменением seed в ECM, но ещё и ускорение работы самого Полларда (он же линейно от rounds зависит). Так что просто один эффект пересилил другой. Чем и плохо такое тестирование всего в комплексе.
А я говорил про то что при одинаковой скорости ECM что с seed=1, что с seed=2 (правда это лишь предположение), улучшение фильтрации должно приводить к уменьшению общего времени - ведь на последующие стадии остаётся меньше цепочек и значит они должны выполняться быстрее. Раз у Вас наоборот медленнее, выходит что seed=2 в ECM работает в среднем медленнее seed=1 и уже это пересиливает ускорение последующих стадий.
И кстати Полларда обычно запускают перед ECM так как он проще и соответственно итерации быстрее.

Я бы ради интереса записал полный список чисел переданных на ECM и запустил бы их проверку с разными seed и поискал бы минимум времени. А потом поменял бы этот список на кардинально другой и снова посмотрел на времена с разными seed. И ещё раз, и ещё, и ещё много раз. Что-то мне подсказывает что по мере накопления статистики оптимальный seed будет гулять в широких пределах, а разница в средней скорости для разных seed будет уменьшаться. Т.е. на большой выборке выбор seed должен быть неважен. Но Вы этого не можете выявить из-за недостаточности выборки и из-за взаимовлияний разных стадий друг на друга.