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

[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) и дальше?

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

[wrest]

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

Что значит "пришибло вероятностями"? Почему меня не "пришибло вероятностями", а вас "пришибло"? В чём безысходность?

Ничего хорошего теперь не найдётся без суперкомпьютера. Нужны какие-то новые идеи по конструированию цепочек, текущие идеи полагаются на распределение простых чисел в дикой природе и соответствующую надежду на удачу. Я заехал немного в тему генерации паттернов, но и при идеальных паттернах, вероятности слишком малы. Как-то так. Тоска-печаль.

[Yadryara]

Ну вас-то это вроде не должно было печалить. Вы же сказали что соревноваться и не собираетесь. Так что не вижу оснований для печали.

К тому же Владимир на днях дал прогноз, что D(192,15) найдётся уже в этом месяце. Или вы 50-100 потоков на 2-3-4 компах уже приравниваете к наличию суперкомпа?

Я тем временем разложил эти 66 74-хзначных числа. Привожу статистику для 11 мест (из 12-ти), где ожидалась сборка pqr.

Ц — номер исходной цепочки
М — номер места
Значн. факт — значность факторов. То есть количество десятичных цифр в найденных факторах.
Д — количество делителей в числе на этом месте
О — количество обязательных простых
П — количество произвольных простых
Т — количество найденных предпростых (вы их любите называть таблицей, поэтому Т)
ВФ — всего факторов в числе на этом месте
Комментарий — прокоментил нестандартную сборку (6 факторов вместо обычных 7)
* — по этой значности можно ориентироваться на количество цифр в частных.

(66)

Ц  М  Значн. факт       Д   О   П   Т    ВФ   Комментарий 

1. 1.     15   51     192   2   2   1     7
1. 2.     12   52     192   2   1   1     6        3^5
1. 3.     24   40     192   1   3   1     7           
1. 4.   8  9   52     192   1   2   0     6        2^3k^2
1. 5.     10   54     192   1   3   1     7
1. 6.     12   53     192   2   1   1     6        5^5
1. 7.     17   46     192   0   4   1     7
1. 8.     19   45     192   2   2   1     7
1. 9.     17   47     192   0   4   1     7
1.10.   8 25   35     192   2   2   0     7
1.11.  11 19   39     192   2   2   0     7

2. 1.     14   52     192   2   2   1     7
2. 2.          61*    192   2   1   2     6
2. 3.   7  8   53     192   1   3   0     7
2. 4.  18 23   29     192   1   2   0     6
2. 5.   8 10   50     192   1   3   0     7
2. 6.     14   52     192   2   1   1     6
2. 7.     11   52     192   0   4   1     7
2. 8.          62*    192   2   2   2     7
2. 9.   7 21   40     192   0   4   0     7
2.10.  12 26   31     192   2   2   0     7
2.11.  11 14   44     192   2   2   0     7

3. 1.     22   43     192   2   2   1     7
3. 2.   7  7   57     192   2   1   0     6
3. 3.          58*    192   1   3   2     7
3. 4.  11 18   41     192   1   2   0     6
3. 5.     17   47     192   1   3   1     7
3. 6.   8 25   36     192   2   1   0     6
3. 7.   9 21   38     192   0   4   0     7
3. 8.      7   58     192   2   2   1     7
3. 9.     13   50     192   0   4   1     7
3.10.   7 28   35     192   2   2   0     7
3.11.     27   40     192   2   2   1     7

4. 1.      7   57     192   2   2   1     7
4. 2.  13 15   42     192   2   1   0     6
4. 3.          59*    192   1   3   2     7
4. 4.     12   55     192   1   2   1     6
4. 5.          63*    192   1   3   2     7
4. 6.     10   55     192   2   1   1     6
4. 7.     18   44     192   0   4   1     7
4. 8.   7 17   46     192   2   2   0     7
4. 9.      8   53     192   0   4   1     7
4.10.     11   53     192   2   2   1     7
4.11.      7   60     192   2   2   1     7

5. 1.     10   54     192   2   2   1     7
5. 2.  17 23   31     192   2   1   0     6
5. 3.     25   37     192   1   3   1     7
5. 4.      8   59     192   1   2   1     6
5. 5.     18   48     192   1   3   1     7
5. 6.     18   48     192   2   1   1     6
5. 7.     17   47     192   0   4   1     7
5. 8.     12   56     192   2   2   1     7
5. 9.          58*    192   0   4   2     7
5.10.      8   55     192   2   2   1     7
5.11.   8 14   48     192   2   2   0     7

6. 1.      7   55     192   2   2   1     7
6. 2.   8 18   44     192   2   1   0     6
6. 3.     25   40     192   1   3   1     7
6. 4.  11 29   30     192   1   2   0     6
6. 5.     10   54     192   1   3   1     7
6. 6.     22   43     192   2   1   1     6
6. 7.     25   38     192   0   4   1     7
6. 8.   8  9   53     192   2   2   0     7
6. 9.   8 11   48     192   0   4   0     7
6.10.   9 28   32     192   2   2   0     7
6.11.   7 26   37     192   2   2   0     7

[Yadryara]

Переставил столбцы в более естественной последовательности — по возрастанию факторов и добавил время. Только это пока (для простоты) время полной факторизации 74-значных чисел с помощью factorint( chislo, 4), а не то что делается или должно делаться в рабочей программе.

И пока запускал в интерпретаторе в одном потоке.

Самые долгие разложения:

Ц  М         О   П   Т  Зн. факт.    ВФ     Д    Time ms

2. 4.        1   2   0   18 23 29     6   192      21555
3.11.        2   2   1      27 40     7   192      13132
5. 5.        1   3   1      18 48     7   192      11693
6. 3.        1   3   1      25 40     7   192       9902
5. 7.        0   4   1      17 47     7   192       9447

Программа

(PARI)

default(parisizemax, 128M);

{obobyaz = 0; obproiz = 0; obsvob = 0;

cc=readvec("20_74_povozr_x11.txt");
t=vector(#cc);

print;


for(i=0,#cc-1,


t0=getwalltime(); F = factorint( cc[i+1], 4); t[i+1]=getwalltime()-t0;


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

print1(i\11 + 1, ". ", i%11 + 1, ".     ");

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

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

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

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


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

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

print("   ", obyaz, "   ", proiz, "   ", svob, "     ", stroka, "     ", matsize(F)[1], "   ", numdiv(cc[i+1]), "       ", t[i+1] );

);

print;print(obobyaz, "   ", obproiz, "   ", obsvob);print;

print;print(t);print;

}quit

[wrest]

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

Программа

У меня на планшете (интерпретатор, в один поток) проработала 683 секунды. Посмотрим.

[Yadryara]

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

У меня на планшете (интерпретатор, в один поток) проработала 683 секунды.

Долго. Если смотрели в код, то надеюсь заметили, что на всякий случай делается ещё и numdiv.

Если вы вопросов не задаёте, значит всё понятно? Итоговые частные это те которые раскладываются либо на 2 либо на три простых фактора в первой степени.
Вот если на три, тогда надо поиск фактора выполнять ещё раз.

[Yadryara]

Поискал ещё D(192,12). Нашёл ещё 39 новых, то бишь для обсуждаемой серии 1-0-11-0 довёл их количество до 45. В этих 45 цепочках $45\cdot12=540$ чисел. Нашлись и покороче: 72 и 73-значные. Для единообразия проверил все 540.

(45)

611142354891569765230302686332186116343885992050683915745888694620256245
8270524074670532399671484627515335041989800251815802192673525572636256245
9266186576049688464673021364017844528144851479450172473102652889909856245
12772696442739943221809077341497956726456499563581607373911653396533856245
15255940403285885548349694319270294697298235174673422385232721165148256245
15510467269353741786670691981065171840454292652038336512888265822581856245
16508460551520046779868027918538908803505796803273145209573319971868256245
18617942953595781097267177355321004617368516335253402280101703911388256245
21139482497672802439223096022180320461579291343066422935689595761372256245
22912979715011050677234063489801789075839832788710264704295668718364256245
23314397983197917381639395693960317128418238441164261240450402365084256245
23774471179311262662016137219519334498535297662998726000770935119759456245
23810554982684706691984152580808040681337834888917679445482271307548256245
26116029641282568727688888895777391111574019817974246175168748092853856245
26312224168260411241527011800317577174205557576749312900680713326735456245
28572167827864311031455307068742679898732876112210366031848283524469856245
29292654122127422394092999322435069539346758303509286912331186308367456245
30470088979000909073642116609093411675480368362620434836912695687311456245
34121421339357612956510451783188830090976882559199447286698558219484256245
35012575872792474989452949908035781770264029829462010486614350780137056245
35305036284051466291328652674880258021088110244715187211796171568437856245
37490237529828734199570104748359083534169939288938711572933322238837856245
39549242830576182219910051971051334482502454804644651268099986965596256245
44643952480747648619794193728994015558844776050532214797442704336693856245
45728818091965287267003587679323701159478374438263805179812510575119456245
48204623328766293973215165071530017886863374001120360971133126711029856245
48481578260903356578717680180878438723282334553263728416323050278159456245
48838220588805561548604875731672680096073018541673041855876338960757856245
53700892855890143158480078121348893863114877107766695619297182088181856245
53886657403578656924132323112580712701460250374746798727701562258805856245
63971136825343048749094978892676683299750421994056100801247474889909856245
65862214750258306272565772507852209917449133557847865609970767853199456245
68266317661664606327183333781435813609832740288225653290206720707881056245
74523945627631922964707914098415363279127089606834626761406518990185056245
78053436266228709024711166556911843681600546376120759465157195567759456245
79603144229598480022983084265112225800769228318294386237223638414671456245
83592054546210872172916455157050866949331649065825624027047462981673056245
83686731866411174175749768792664785899928111307893453676114205141993056245
86648014931756205475147227427458592895262180012557668963278620923676256245
88444950680487500586673928500369745884163184657358809316449021576437856245
91042855548523859314234936324022232922092560017147259246657180332815456245
92277738044216335408810706337747172823791697406637445855810437465551456245
96798924036621854908816719894830810664183507951443747958050132753103456245
97909343682748705170771989473720682118744813289420695897317369528924256245
99471308849189565569519524313540894542647444653689835226307122441653856245

Добавил ещё одну колонку, где указываю время для numdiv. Изменённая программа:

(PARI)

default(parisizemax, 128M);

{obobyaz = 0; obproiz = 0; obsvob = 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 = "";

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

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


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

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

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

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


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

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

t0=getwalltime(); nmdv = numdiv(n[nomcep] + dobmes); t2=getwalltime()-t0;


print("   ", obyaz, "   ", proiz, "   ", svob, "     ", stroka, "     ", matsize(F)[1], "   ", nmdv, "       ", t1, "     ", t2 );

write("log1.txt", "   ", obyaz, "   ", proiz, "   ", svob, "     ", stroka, "     ", matsize(F)[1], "   ", nmdv, "       ", t1, "     ", t2 );

));

print;print(obobyaz, "   ", obproiz, "   ", obsvob);print;


}quit

[wrest]

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

Если смотрели в код, то

Нет не смотрел. Я воспринимаю это как "эталонную программу".
Она у меня работала 683 сек. Если то что напишу я, будет делать то же, но работать будет быстрее - значит удалось ускорить.

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

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

Поискал ещё D(192,12). Нашёл ещё 39 новых, то бишь для обсуждаемой серии 1-0-11-0 довёл их количество до 45. В этих 45 цепочках $45\cdot12=540$ чисел. Нашлись и покороче: 72 и 73-значные. Для единообразия проверил все 540.

Ладно, я пока сдаюсь. Объяснить вам подход к ускорению через установление общих единиц измерения либо мне не удалось либо подход вам не подходит. Ищите :)