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

[wrest]

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

Так второй получается банальным делением исходного числа на найденный первый делитель. И оба в принципе могут быть составными.

Я посмотрел на код полларда в pari. Он проверяет найденный делитель на простоту, и если составной, то пытается по-быстрому разложить. Если получилось, возвращает два множителя и остаток(частное). Если нет - возвращает неразложенный множитель и остаток(частное). Вроде как-то так. Остаток(частное) на простоту не проверяет и раскладывать не пытается.

[Dmitriy40]

wrest
Ну вот и нашли откуда может три делителя взяться.
Интересно, а если найденный делитель имеет не два, и три и более делителей, что будет? Все три (или минимум два кроме первого) числа могут оказаться составными или вернётся больше чисел? Это конечно довольно теоретический интерес, можете не ковыряться, вероятность такого события околонулевая, но вдруг ...

[wrest]

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

можете не ковыряться,

Вообще код pari/gp тот ещё "подарок" в смысле чтения.

[Yadryara]

Проверил Поллардом вроде бы уже все расклады для разностей 1, 2, 3. И на том самом тестовом наборе получился 100%-й запрет:

5-й фильтр прошли  57 цепочек
6-й фильтр прошли   7
7-й фильтр прошли   0                  1min, 17,612 ms

Поменял расстановку и одна цепочка всё-таки просочилась через все фильтры:

5-й фильтр прошли  45 цепочек
6-й фильтр прошли   9
7-й фильтр прошли   1                  1min, 16,326 ms

Кстати, одно из её чисел имеет в разложении и 26-значный фактор и 29-значный кофактор.

Ещё одна расстановка:

5-й фильтр прошли  54 цепочки
6-й фильтр прошли  10
7-й фильтр прошли   0                  1min, 19,038 ms

[Yadryara]

Ну и другие проскакивания тоже были. Грубо говоря, за 17 минут в одном потоке, 4 штуки нашлись. И все с низким vаlids. Это многовато. Для одного потока лучше в среднем 1 приближение в час, а то и меньше.

Детально разбирался с проскочившей цепочкой. Она начинается с числа:

7120610856227179156735278559275507481639987000962322343925

Как и полагается, 58-значная. Это пока разрешённый максимум. То есть поиск идёт среди чисел 0 — 1e58.

Дельта равна 1

Комп взял самое большое частное, 54-значное, которое на 4-м месте:
109037897467646379344837660162861501311404921612187957
4   [0, 0, 0, 0]                  и не смог найти 11-значный фактор.

Взял 2-е по величине частное, 53-значное, которое на 1-м месте:
46700185972960676548517977106250254019609686840218543
1   [0, 0, 0, 0]                  и не смог найти 13-значный фактор.

Взял 3-е по величине частное, 51-значное, которое на 16-м месте:
328087646082185316606688845667149885485117387290013
16   [0, 0, 0, 0]                 и не смог найти 15-значный фактор.

Взял 4-е по величине частное, 50-значное, которое на 13-м месте:
26055127621162678006287911543446813262120924335409
13   [11, 665, 110922797, 234894253713803105833040899098918442005397]
И нашёл 9-значный фактор. Превышения нет, число имеет ровно 96 делителей.

Взял 5-е по величине частное, 50-значное, которое на 20-м месте:
12824825236451080991634591671334071785930335893563
20   [0, 0, 0, 0]                 и не смог найти 13-значный фактор.

Взял 6-е по величине частное, 49-значное, которое на 6-м месте:
1269948885612131373911916122048844489909547214539
6   [1, 818, 8392843, 151313313690263403463154990752102057659073]   
И нашёл 7-значный фактор. Превышения нет, число имеет ровно 96 делителей.

Взял 7-е по величине частное, 46-значное, которое на 15-м месте:
2743805295392292163577452029396388136731761139
15   [0, 0, 0, 0]                 и не смог найти 16-значный фактор.

Перешёл к 7-й фильтрации:

Дельта больше 1-цы

Комп взял самое большое частное, 56-значное, которое на 8-м месте:
26569443493384996853489845370430998065820847018516128149
8   [0, 0, 0, 0]                  и не смог найти 15-значный фактор.

Далее он брал всё меньшие и меньшие частные:

Частное                                                 Место  Рез. Полларда  Фактор
24219764817099248832432920269644583270884309527082729061   10   [0, 0, 0, 0]      19-знач.
3476860769642177322624647734021243887519524902813633957    12   [0, 0, 0, 0]      20
1922930287936046221100534312523766535684576559806190209     3   [0, 0, 0, 0]      26
148117711366376402145344230962173055739900715583523783     18   [0, 0, 0, 0]      14
6773393175276172026321962136247203343828643098449599       14   [0, 0, 0, 0]       9
4764834028855004993101138014610128473289432144053149       17   [0, 0, 0, 0]      18
3020570294233105731140247453107975480180687146651091       19   [0, 0, 0, 0]      16
148127364880420799498691766039408182124944553235587         5   [0, 0, 0, 0]      17
3163208355216483478367422972601381026000399355873           7   [0, 0, 0, 0]      13
2840230567188292962208161557529549856063375268819           9   [0, 0, 0, 0]      10

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

[wrest]

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

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

Добавить итераций полларду можно, но поллард тут уже или не найдёт или будет медленнее встроенного factorint().
Попробуйте на 7-й фильтрации factorint(p,4) и/или factorint(p,6)

[Yadryara]

Спасибо. Но я всё никак с алгоритмом Полларда не наиграюсь. И выяснилось, что и быстрее и эффективнее не менять константу, а увеличить количество итераций.

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

Осталось цепочек после фильтров                Время     Констант*
       3      4    5   6   7                              итераций
[ 836203, 14469, 186, 32, 10 ]       6min, 21,080 ms     280*  300
[ 836203, 14469, 186, 32,  5 ]       5min, 36,111 ms      40* 2100
[ 836203, 14469, 186, 32,  2 ]       5min, 12,327 ms      30* 2800
[ 836203, 14469, 186, 32,  3 ]       5min, 14,080 ms      21* 4000
[ 836203, 14469, 186, 32,  2 ]       5min, 13,183 ms      10* 8400
[ 836203, 14469, 186, 32,  0 ]       4min, 42,133 ms       1*84000

Здесь менялось соотношение только для 7-й фильтрации, что видно по векторам.

Ну и затем уже смелее поменял и для 6-й фильтрации и для большего поиска.

        3      4    5    6  7                                6         7
[ 2927724, 50711, 582, 116, 2 ]   16min, 46,894 ms    21* 1500   1*84000
[ 2927724, 50711, 582,  64, 1 ]   15min, 52,503 ms     1*30000   1*84000

Но всё равно находится многовато приближений. В одном потоке в среднем по 11 штук в час.

[Yadryara]

Решил более детально разобрать процесс фильтрации цепочек.

Серия нынче 0-0-10-10-0-9! То есть нужно найти 8 делителей на одних 10 местах и 16 делителей на других 10 местах.

Упрощённо: нужно найти либо 3, либо 4 неизвестных фактора.

Имеется частное, которое пока считается за один фактор. То есть имеется 20 единичек, а нужно 10 3-к и 10 4-к. Упростим и запишем, что на первых 10 местах нужно найти 3, а на вторых десяти местах — 4 фактора.

План      33333333334444444444
Факт      11111111111111111111

Для простоты запишем сразу дельту:

План - Факт = 22222222223333333333

Далее идёт проверка по предвычисленным простым до $2^{20]$. Начиная с 79. Допустим, первая же попытка удачная: на 79 делится 1-е же число цепочки. И дельта уже

12222222223333333333

Далее проверяем делимость на 83. Допустим, что и вторая попытка удачная: 1-е же число цепочки разделилось и на 83. И дельта уже такая:

02222222223333333333

Факторов стало столько сколько надо. И, вполне возможно, что на первом месте уже есть подходящее число делителей, в данном случае 96. И, если это не так, то уже сейчас можно отбросить цепочку.

Проверяем частное самой быстрой командой !ispseudorprime(cha,1).

Насколько понимаю, эта команда не ошибается, то есть ежели команда определила, что частное составное, то оно составное. А это значит, что в разложении частного есть ещё как минимум один фактор, а значит имеется перебор. Перебор очень хорош тем, что другие степени факторов можно и не смотреть.

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

Ну а ежели частное не оказалась составным, цепочку пока не отбрасываем, продолжаем проверку дальше.

Далее проверяем делимость на 89. Допустим, что и третья попытка удачная. Только частное 1-го числа цепочки уже не может на него разделиться и не может ему равняться, потому что оно огромное, уж никак не меньше 40 знаков. Допустим, что разделилось 2-е число цепочки. Дельта стала такой:

01222222223333333333

Проверять пока нечего: новый нолик не появился.

Дальше делим на 97. Если нолик появился, так же проверяем частное на том месте где он появился.

Продолжаем эту проверку на предпростых до $2^{20]$. Если ни одного основания отбросить цепочку так и не возникло, 4-ю фильтрацию считаем законченной. Дельта по итогам этого этапа проверок может быть например такой:

00000111112222233333

Все 5 мест с ноликами я считаю пока годными. И далее уже работаю с 15-ю оставшимися местами. Потому и назвал векторы ostmes, ostmes1, ostmes2.

[wrest]

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

Далее проверяем делимость на 89. Допустим, что и третья попытка удачная. Только частное 1-го числа цепочки уже не может на него разделиться

Почему?

[Yadryara]

wrest, ведь обоснование идёт сразу же. Почеркнул:

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

Далее проверяем делимость на 89. Допустим, что и третья попытка удачная. Только частное 1-го числа цепочки уже не может на него разделиться и не может ему равняться, потому что оно огромное, уж никак не меньше 40 знаков.

Или оно вам непонятно? Или вы с ним не согласны?

[wrest]

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

Или оно вам непонятно? Или вы с ним не согласны?

В обосновании написано что частное не равно 89 потому что частное больше на 38 порядков. Эта часть понятна. А почему частное заведомо не делится на 89 -- непонятно.

[Yadryara]

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

А почему частное заведомо не делится на 89 -- непонятно.

Тут довольно тонкий момент. Может я ошибаюсь, но неужели более ранняя проверка !ispseudorprime(cha,1) не отловит такой крошечный фактор, как 89?

[wrest]

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

Может я ошибаюсь, но неужели более ранняя проверка !ispseudorprime(cha,1) не отловит такой крошечный фактор, как 89?

А... надо освежить в памяти что мы ранее обсуждали.
В em3() который я тут ранее пкбликовал, это вроде не имеет значения. Там сразу видно делится ли какое-нибудь число из цепочки на очередное простое из таблицы или нет.

[Yadryara]

Конечно надо освежить.

Но я не стал ждать милости от природы — взял да и проверил много всяких произведений на 38-ми и на 56-значное простое:

{t0=getwalltime();print;
kpod = 0; neotlov = 0;

forprime( p = 79, 2^22,

\\20148766517543347947282101683535543641;

n = p * 18352089835637059682307418967204916189793780930315263773;

if( !ispseudoprime(n,1), kpod++ , neotlov++;print(neotlov) );

);
print;print(kpod, "   ", neotlov);print;

print;print(strtime(getwalltime()-t0));print;
}quit;


295926   0         2,226 ms
295926   0         3,815 ms

[Yadryara]

Итак, в 4-й фильтрации ошибок не выявлено. Составные пока ищутся прекрасно — быстро и все до единого.

5-я фильтрация пока реализована так:

Проход по всем оставшимися местам и для тех мест, где дельта больше нуля, то есть в примере как раз для 15-ти, и для каждого места тоже осуществляется проверка по псевде, но уже другая:

ispseudoprime(cha)

Считаем что она равна строгой проверке на простоту. Ну, а если частное уже простое, значит имеется недобор факторов. И цепочка отбрасывается.

НО. С недобором ситуация не такая простая как с перебором. Надо перепроверить, посмотреть на степени простых выше первой.

Случай 1. Нам надо собрать 8 делителей. Но факторов у нас не 3, а меньше. 8 делителей можно собрать с одним фактором, если он будет простым в 7-й степени, либо с двумя факторами, если один из них будет простым в 3-й степени, а другой — простым в 1-й степени.

Случай 2. Нам надо собрать 16 делителей. Но факторов у нас не 4, а меньше. 16 делителей можно собрать с одним фактором, если он будет простым в 15-й степени. Либо с двумя факторами,

если один из них будет простым в 7-й степени, а другой — простым в 1-й степени

или

если оба будут простыми в 3-й степени.

Либо с тремя факторами,

если один из них будет простым в 3-й степени, а два других — простыми в 1-х степенях.

И, вроде бы, на данный момент это игнорируется, то есть потенциально годная цепочка могла быть отброшена?