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

[Yadryara]

wrest, спасибо. Более актуальны бо́льшие числа. Я выше привёл 6 штук. Это же на самом деле не 6 чисел, а 66:

(Оффтоп)

15510467269353741786670691981065171840454292652038336512888265822581856245
15510467269353741786670691981065171840454292652038336512888265822581856246
15510467269353741786670691981065171840454292652038336512888265822581856247
15510467269353741786670691981065171840454292652038336512888265822581856248
15510467269353741786670691981065171840454292652038336512888265822581856249
15510467269353741786670691981065171840454292652038336512888265822581856250
15510467269353741786670691981065171840454292652038336512888265822581856251
15510467269353741786670691981065171840454292652038336512888265822581856252
15510467269353741786670691981065171840454292652038336512888265822581856253
15510467269353741786670691981065171840454292652038336512888265822581856254
15510467269353741786670691981065171840454292652038336512888265822581856255
26312224168260411241527011800317577174205557576749312900680713326735456245
26312224168260411241527011800317577174205557576749312900680713326735456246
26312224168260411241527011800317577174205557576749312900680713326735456247
26312224168260411241527011800317577174205557576749312900680713326735456248
26312224168260411241527011800317577174205557576749312900680713326735456249
26312224168260411241527011800317577174205557576749312900680713326735456250
26312224168260411241527011800317577174205557576749312900680713326735456251
26312224168260411241527011800317577174205557576749312900680713326735456252
26312224168260411241527011800317577174205557576749312900680713326735456253
26312224168260411241527011800317577174205557576749312900680713326735456254
26312224168260411241527011800317577174205557576749312900680713326735456255
28572167827864311031455307068742679898732876112210366031848283524469856245
28572167827864311031455307068742679898732876112210366031848283524469856246
28572167827864311031455307068742679898732876112210366031848283524469856247
28572167827864311031455307068742679898732876112210366031848283524469856248
28572167827864311031455307068742679898732876112210366031848283524469856249
28572167827864311031455307068742679898732876112210366031848283524469856250
28572167827864311031455307068742679898732876112210366031848283524469856251
28572167827864311031455307068742679898732876112210366031848283524469856252
28572167827864311031455307068742679898732876112210366031848283524469856253
28572167827864311031455307068742679898732876112210366031848283524469856254
28572167827864311031455307068742679898732876112210366031848283524469856255
30470088979000909073642116609093411675480368362620434836912695687311456245
30470088979000909073642116609093411675480368362620434836912695687311456246
30470088979000909073642116609093411675480368362620434836912695687311456247
30470088979000909073642116609093411675480368362620434836912695687311456248
30470088979000909073642116609093411675480368362620434836912695687311456249
30470088979000909073642116609093411675480368362620434836912695687311456250
30470088979000909073642116609093411675480368362620434836912695687311456251
30470088979000909073642116609093411675480368362620434836912695687311456252
30470088979000909073642116609093411675480368362620434836912695687311456253
30470088979000909073642116609093411675480368362620434836912695687311456254
30470088979000909073642116609093411675480368362620434836912695687311456255
63971136825343048749094978892676683299750421994056100801247474889909856245
63971136825343048749094978892676683299750421994056100801247474889909856246
63971136825343048749094978892676683299750421994056100801247474889909856247
63971136825343048749094978892676683299750421994056100801247474889909856248
63971136825343048749094978892676683299750421994056100801247474889909856249
63971136825343048749094978892676683299750421994056100801247474889909856250
63971136825343048749094978892676683299750421994056100801247474889909856251
63971136825343048749094978892676683299750421994056100801247474889909856252
63971136825343048749094978892676683299750421994056100801247474889909856253
63971136825343048749094978892676683299750421994056100801247474889909856254
63971136825343048749094978892676683299750421994056100801247474889909856255
99471308849189565569519524313540894542647444653689835226307122441653856245
99471308849189565569519524313540894542647444653689835226307122441653856246
99471308849189565569519524313540894542647444653689835226307122441653856247
99471308849189565569519524313540894542647444653689835226307122441653856248
99471308849189565569519524313540894542647444653689835226307122441653856249
99471308849189565569519524313540894542647444653689835226307122441653856250
99471308849189565569519524313540894542647444653689835226307122441653856251
99471308849189565569519524313540894542647444653689835226307122441653856252
99471308849189565569519524313540894542647444653689835226307122441653856253
99471308849189565569519524313540894542647444653689835226307122441653856254
99471308849189565569519524313540894542647444653689835226307122441653856255

Надо из них выделить частные и какие-то разложить. Потому что не все надо раскладывать, некоторые и так дали 192 делителя.

[wrest]

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

Надо из них выделить частные и какие-то разложить. Потому что не все надо раскладывать, некоторые и так дали 192 делителя.

Хорошо, значит про предыдущие числа забыли и ввкинули на помойку.
Начинаем сначала. Есть числа. Где "эталонная" функция, ко орая это делает, и за какое время (на вашем компе) она это делает, и какой, глауное, результат вам нужен?

[Yadryara]

Попробую продолжить объяснение. Попался деду Мазаю трудный гриб. Засел он в земле, как репка. Тянет-потянет — вытянуть не может. Но решил не сдаваться.

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

И принёс-то он всего-навсего десять штук за 5 часов. А как же гонщик, который не то что даже под кусты заглядывать ленился, а из машины выходить? По-прежнему только лёгкие, которые на видных местах были, хватал на ходу, но проехать он успел много и собрал за те же 5 часов 50 грибов.

— Посмотрите, какого я огромного одолел и притаранил! Посчитайте его одного за 10.
— Нет, Мазай Мазаевич, у нас по регламенту каждый гриб за одну штуку считается, будь он даже хоть с дом размером.

Ну, мораль, надеюсь, понятна. Нужно найти какой-то оптимум и не тратить сильно много времени на трудные числа, вовремя бросать и искать другие. Тем более что паттернов для 96 и тем более для 192-х делителей очень много и есть где поискать.

[wrest]

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

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

Что это значит-то? Вы же с Квеном писали таймер с точностью до миллисекунд, я только не помню работает он у вас или нет. Если работает, ну ставьте таймер на "немного времени".
Расклад по времени факторизации я дал вам выше, ну вы можете оттуда понять, что значит "сильно много"?
ECM работает детерминировано: вы можете, опять же, померить у себя, сколько rounds задавать и какой B1 чтобы ECM заканчивал те числа, которые он не может разложить, в среднем за столько-то мс.

[Yadryara]

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

Вы же с Квеном писали таймер с точностью до миллисекунд, я только не помню работает он у вас или нет.

Работал, да. Даже до микросекунд. Но потом, когда стал применять алгоритм Полларда, он стал не нужен — ведь время хорошо регулируется количеством итераций. Как понимаю, для ЕСМ это последний параметр — b1. Вот, кстати:

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

А вот так получилось:

resecm = my_ecm(cha = cha/resecm, 120, 1, 60000);

Если взять не 60 тысяч а, 25 тысяч, то не раскладывает то трудное число, а если взять 29 тысяч — раскладывает за заметно меньшее время, хотя и не вдвое быстрей чем при 60-ти тысячах.

У вас-то как дела? Вы изучали D(24,6) потом D(48,6), а дальше? До 96-ти делителей руки пока не дошли? Или пошли снова к длинным цепочкам, например, D(48,15). Или что? Ведь совсем не бросили?

[wrest]

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

Как понимаю, для ЕСМ это последний параметр — b1. Вот, кстати:

Оба параметра, rounds (количество кривых) и B1.
От rounds зависит примерно линейно, от B1 непонятно как но при росте B1 время растёт. Но это тоже проверить можно на ваших тайных числах.

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

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

У вас-то как дела? Вы изучали D(24,6) потом D(48,6), а дальше?

Дальше нет новых идей, меня пришибло вероятностями, всё выглядит как-то безысходно.

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

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

Если взять не 60 тысяч а, 25 тысяч, то не раскладывает то трудное число, а если взять 29 тысяч — раскладывает за заметно меньшее время, хотя и не вдвое быстрей чем при 60-ти тысячах.

Брать надо не так :)
Надо брать возрастающие B1, из этой последовательности:
[500,520,560,620,700,800,900,1000,1150,1300,1450,1600,1800,2000,2200,2450,2700,2950,3250,3600,4000,4400,4850,5300,5800,6400]
Если мало, могу добавить. И делать по 1..3 заходам (rounds). Так мне думается будет оптимальнее.
Для тех 270 которые вы уже вычеркнули как ненужные, я бы начинал с B1=800.
Ну или вы можете дать команду\g 4 и потом факторизовать встроенным фактором ваше число, там в отладочной печати будет видно с какого B1 начинает pari/gp

[Dmitriy40]

B1 для ECM выбирается в зависимости от ожидаемой разрядности меньшего делителя.
Так что для примерно одинаковых чисел и мест pq, pqr, pqrs, pqrst желательно брать разные B1.
Но зависимость не абсолютно жёсткая, даже для меньших B1 делитель вполне может найтись, сразу или через сколько-то повторов (кривых, rounds). И даже не обязательно прям меньший. Это Вы выше и сами видели.
Если ECM вызывается повторно для того же числа, то я бы обязательно менял seed (можно просто всегда ставить случайное число), это исключит повторение уже вычисленных эллиптических кривых.
Rounds это количество повторов (эллиптических кривых). Чем больше повторов, тем выше вероятность найти делитель, даже при недостаточном B1. Зависимость экспоненциальная, так что большие rounds по идее выгоднее, YAFU и другие факторизаторы делают и тысячи rounds (для 40+ значных делителей), я уже показывал табличку от одного такого (YAFU почти 100% совпадает с ней):

Используется синтаксис Text

digits D  optimal B1   default B2           expected curves
                                                N(B1,B2,D)
                                       -power 1         default poly
   20       11e3         1.9e6             74               74 [x^1]
   25        5e4         1.3e7            221              214 [x^2]
   30       25e4         1.3e8            453              430 [D(3)]
   35        1e6         1.0e9            984              904 [D(6)]
   40        3e6         5.7e9           2541             2350 [D(6)]
   45       11e6        3.5e10           4949             4480 [D(12)]
   50       43e6        2.4e11           8266             7553 [D(12)]
   55       11e7        7.8e11          20158            17769 [D(30)]
   60       26e7        3.2e12          47173            42017 [D(30)]
   65       85e7        1.6e13          77666            69408 [D(30)]

   Table 1: optimal B1 and expected number of curves to find a factor of D digits with GMP-ECM.

After performing the expected number of curves from Table 1, the probability that a factor of D digits was missed is exp(-1), i.e., about 37%. After twice the expected number of curves, it is exp(-2), i.e., about 14%, and so on.

Example: after performing 7553 curves with B1=43e6 and B2=2.4e11, the probability to miss a 50-digit factor is about 37%.

Здесь в первой колонке значность ожидаемого делителя, во второй значение B1, в самой правой rounds (количество кривых). Такой выбор даёт вероятность найти делитель порядка 63%. Для других значений rounds вероятность несложно прикинуть по процитированной словами формуле. В PARI значения rounds могут быть немного другими, не знаю какие он полиномы использует, но зависимости будут те же.

Время работы удобнее регулировать через rounds, B1 влияет скорее на саму возможность достаточно быстрого нахождения делителя желаемой значности (если B1 сильно меньше необходимого то придётся искать долго, т.е. проверить много кривых/rounds). Точной зависимости вероятности от B1 не знаю, но можно попытаться вывести из табличных данных выше, только зачем.
Сильно завышать B1 тоже невыгодно так как падает скорость работы (числа больше и вообще).

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

Я бы предложил B1 выбирать как и порог для factor - сначала достаточно малый для всех мест цепочки (не обязательно одинаковый для всех, см. выше), потом больше на полпорядка (раза в 3-4, это примерно плюс 5 цифр делителя) снова для всех и так далее пока время не кончится или цепочка не отбросится или не разложится вся.
И rounds тоже начинать с малых, буквально 1-3, потом можно увеличивать. Его значения можно прикинуть по формуле и желаемой вероятности.

[Yadryara]

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

Но это тоже проверить можно на ваших тайных числах.

?? Какие ещё тайные числа?? Ещё и курсивом выделено. Вы же раньше не были склонны к конспирологии. Хоть я его и не люблю, но так и хочется поставить мордоладонный смайлик

Я же числа показываю, в чём вы видите тайну-то??

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

Для тех 270 которые вы уже вычеркнули как ненужные,

Я их не вычеркнул как ненужные! Просто я перешёл от D(96,11) к D(96,12) и числа стали гораздо больше. Планово перешёл. Я же показывал в таблице. Ну вот ещё раз:

6-поточный счёт

Кортеж         Серия   Обсчитано   2^   n от   Найдено     Время   Милсек/   Скорость
                       паттернов        0 до   D(192,L)   секунд   паттерн   корт/сут

D(192, 7)   1-0- 6-0         360   17   1e43      1464       522      1449     242526
D(192, 8)   1-0- 7-0         180   18   1e50       160       283      1567      49011
D(192, 9)   1-0- 8-0        1440   18   1e55       162       961       667      14570
D(192,10)   1-0- 9-0        4320   19   1e61       104      2374       549       3786
D(192,11)   1-0-10-0       52800   19   1e66       100      8784       166        984
D(192,12)   1-0-11-0        9000   20   1e74         6      3911       435        133
D(192,13)   
D(192,14)   
D(192,15)   

Видите как растут числа? От 1e43 до 1e74. А какими они будут для D(192,15) и D(192,16) ? Ведь именно поэтому вновь встал вопрос о взятии под контроль факторизации, что числа стали огромными.

И вот я решил попытаться ускорить программу, прежде чем попытаться достичь 100 находок. И ровно те 6 находок показал. А есть ещё и другие находки в других трёх сериях, я их не показывал. Мне их тоже показать? Они не тайные, просто не горю желанием ещё больше заваливать тему статистикой. Так показывать?

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

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

У вас-то как дела? Вы изучали D(24,6) потом D(48,6), а дальше?

Дальше нет новых идей, меня пришибло вероятностями, всё выглядит как-то безысходно.

Что-то я не догоняю. Разве это не вы предлагали выражаться ясно? Что значит "пришибло вероятностями"? Почему меня не "пришибло вероятностями", а вас "пришибло"? В чём безысходность? Что мешает перейти, например, к D(96,6) и дальше?

Дальнейшее прокомментирую позже.