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

[Dmitriy40]

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

А что было бы у вас, какие оптимальные B1 и rounds?

Консоль:

>yafu-x64.exe "factor(24148925432634573196763136754090576178896835988651533646083)"
warning: could not open yafu.ini, no options parsed


fac: factoring 24148925432634573196763136754090576178896835988651533646083
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
fac: no tune info: using qs/snfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 3, starting 1000 iterations on C59
rho: x^2 + 2, starting 1000 iterations on C59
rho: x^2 + 1, starting 1000 iterations on C59
pm1: starting B1 = 150K, B2 = gmp-ecm default on C59
ecm: 30/30 curves on C59, B1=2k, B2=gmp-ecm default
ecm: 3/45 curves on C59, B1=11k, B2=gmp-ecm default

starting SIQS on c42: 264428840328183075985530723628329896145301

==== sieving in progress (1 thread):     864 relations needed ====
====           Press ctrl-c to abort and save state           ====
887 rels found: 432 full + 455 from 3842 partial, (63790.09 rels/sec) ETA 0 sec)

SIQS elapsed time = 0.1070 seconds.
Total factoring time = 0.9490 seconds


***factors found***
P17 = 91324854742256183
P18 = 119961603280218769
P25 = 2204278978420309489529029

***factorization:***
24148925432634573196763136754090576178896835988651533646083=91324854742256183*119961603280218769*2204278978420309489529029

ans = 1

Лог:

05/17/26 18:29:26, ****************************
05/17/26 18:29:26, Starting factorization of 24148925432634573196763136754090576178896835988651533646083
05/17/26 18:29:26, using pretesting plan: normal
05/17/26 18:29:26, no tune info: using qs/gnfs crossover of 95 digits
05/17/26 18:29:26, no tune info: using qs/snfs crossover of 95 digits
05/17/26 18:29:26, ****************************
05/17/26 18:29:26, rho: x^2 + 3, starting 1000 iterations on C59
05/17/26 18:29:26, rho: x^2 + 2, starting 1000 iterations on C59
05/17/26 18:29:26, rho: x^2 + 1, starting 1000 iterations on C59
05/17/26 18:29:27, pm1: starting B1 = 150K, B2 = gmp-ecm default on C59
05/17/26 18:29:27, current ECM pretesting depth: 0.000000
05/17/26 18:29:27, scheduled 30 curves at B1=2000 toward target pretesting depth of 18.153846
05/17/26 18:29:27, Finished 30 curves using GMP-ECM method on C59 input, B1=2k, B2=gmp-ecm default
05/17/26 18:29:27, current ECM pretesting depth: 15.177725
05/17/26 18:29:27, scheduled 45 curves at B1=11000 toward target pretesting depth of 18.153846
05/17/26 18:29:27, prp17 = 91324854742256183 (curve 4 stg2 B1=11000 sigma=950782668 thread=0)
05/17/26 18:29:27, Finished 3 curves using GMP-ECM method on C59 input, B1=11k, B2=gmp-ecm default
05/17/26 18:29:27, final ECM pretested depth: 15.380428
05/17/26 18:29:27, scheduler: switching to sieve method
05/17/26 18:29:27, starting SIQS on c42: 264428840328183075985530723628329896145301
05/17/26 18:29:27, random seed: 9030702196905949958
05/17/26 18:29:27, ==== sieve params ====
05/17/26 18:29:27, n = 42 digits, 138 bits
05/17/26 18:29:27, factor base: 800 primes (max prime = 13099)
05/17/26 18:29:27, single large prime cutoff: 654950 (50 * pmax)
05/17/26 18:29:27, using AVX2 enabled 32k sieve core
05/17/26 18:29:27, sieve interval: 1 blocks of size 32768
05/17/26 18:29:27, polynomial A has ~ 5 factors
05/17/26 18:29:27, using multiplier of 1
05/17/26 18:29:27, using multiplier of 1 (kn mod 8 == 5)
05/17/26 18:29:27, using SPV correction of 21 bits, starting at offset 33
05/17/26 18:29:27, trial factoring cutoff at 36 bits
05/17/26 18:29:27, ==== sieving started (1 thread) ====
05/17/26 18:29:27, trial division touched 93899 sieve locations out of 11075584
05/17/26 18:29:27, total reports = 93899, total surviving reports = 20225
05/17/26 18:29:27, total blocks sieved = 338, avg surviving reports per block = 59.84
05/17/26 18:29:27, 887 relations found: 432 full + 455 from 3842 partial, using 169 polys (15 A polys)
05/17/26 18:29:27, on average, sieving found 25.29 rels/poly and 63790.09 rels/sec
05/17/26 18:29:27, trial division touched 93899 sieve locations out of 11075584
05/17/26 18:29:27, ==== post processing stage (msieve-1.38) ====
05/17/26 18:29:27, QS elapsed time = 0.0670 seconds.
05/17/26 18:29:27, begin singleton removal with 4274 relations
05/17/26 18:29:27, reduce to 1270 relations in 2 passes
05/17/26 18:29:27, recovered 1270 relations
05/17/26 18:29:27, recovered 169 polynomials
05/17/26 18:29:27, attempting to build 887 cycles
05/17/26 18:29:27, found 887 cycles from 1270 relations in 1 passes
05/17/26 18:29:27, distribution of cycle lengths:
05/17/26 18:29:27,    length 1 : 432
05/17/26 18:29:27,    length 2 : 455
05/17/26 18:29:27, largest cycle: 2 relations
05/17/26 18:29:27, matrix is 800 x 887 (0.1 MB) with weight 15955 (17.99/col)
05/17/26 18:29:27, sparse part has weight 15955 (17.99/col)
05/17/26 18:29:27, filtering completed in 3 passes
05/17/26 18:29:27, matrix is 749 x 813 (0.1 MB) with weight 14279 (17.56/col)
05/17/26 18:29:27, sparse part has weight 14279 (17.56/col)
05/17/26 18:29:27, commencing Lanczos iteration
05/17/26 18:29:27, memory use: 0.1 MB
05/17/26 18:29:27, lanczos halted after 13 iterations (dim = 747)
05/17/26 18:29:27, recovered 63 nontrivial dependencies
05/17/26 18:29:27, prp18 = 119961603280218769
05/17/26 18:29:27, prp25 = 2204278978420309489529029
05/17/26 18:29:27, Lanczos elapsed time = 0.0360 seconds.
05/17/26 18:29:27, Sqrt elapsed time = 0.0010 seconds.
05/17/26 18:29:27, SIQS elapsed time = 0.1070 seconds.
05/17/26 18:29:27, 
05/17/26 18:29:27, 
05/17/26 18:29:27, Total factoring time = 0.9490 seconds

Видим что ECM нашёл один 17-значный делитель при B1=11e3 на четвёртой кривой из распланированных 45 (вместо 74), а при B1=2e3 все 30 кривых делителя не нашли.
Да, YAFU планирует меньше кривых если число не точно кратное 5 цифр. Здесь он собирался искать делители до 18.153846 цифр.
После нахождения делителя на 42 значное число натравили SIQS (другая разновидность QS вместо MPQS в PARI).

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

Ещё можно заметить что после обработки B1=2e3 и 30 кривых достигли 15.177725 значных делителей, а реальный 16.96 значный делитель нашёлся при достижении 15.380428 значности делителей.

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

Другой запуск, только ECM (лог):

05/17/26 18:49:42, ****************************
05/17/26 18:49:42, Starting factorization of 24148925432634573196763136754090576178896835988651533646083
05/17/26 18:49:42, using pretesting plan: custom
05/17/26 18:49:42, custom pretest ratio is: 0.8000
05/17/26 18:49:42, no tune info: using qs/gnfs crossover of 95 digits
05/17/26 18:49:42, no tune info: using qs/snfs crossover of 95 digits
05/17/26 18:49:42, ****************************
05/17/26 18:49:42, rho: x^2 + 3, starting 1000 iterations on C59
05/17/26 18:49:42, rho: x^2 + 2, starting 1000 iterations on C59
05/17/26 18:49:42, rho: x^2 + 1, starting 1000 iterations on C59
05/17/26 18:49:42, pm1: starting B1 = 150K, B2 = gmp-ecm default on C59
05/17/26 18:49:42, current ECM pretesting depth: 0.000000
05/17/26 18:49:42, scheduled 30 curves at B1=2000 toward target pretesting depth of 47.200000
05/17/26 18:49:43, prp17 = 91324854742256183 (curve 14 stg2 B1=2000 sigma=1439936234 thread=0)
05/17/26 18:49:43, Finished 13 curves using GMP-ECM method on C59 input, B1=2k, B2=gmp-ecm default
05/17/26 18:49:43, current ECM pretesting depth: 0.000000
05/17/26 18:49:43, scheduled 17 curves at B1=2000 toward target pretesting depth of 33.600000
05/17/26 18:49:43, Finished 17 curves using GMP-ECM method on C42 input, B1=2k, B2=gmp-ecm default
05/17/26 18:49:43, current ECM pretesting depth: 15.177725
05/17/26 18:49:43, scheduled 74 curves at B1=11000 toward target pretesting depth of 33.600000
05/17/26 18:49:44, prp18 = 119961603280218769 (curve 40 stg1 B1=11000 sigma=1645361297 thread=0)
05/17/26 18:49:44, Finished 39 curves using GMP-ECM method on C42 input, B1=11k, B2=gmp-ecm default
05/17/26 18:49:44, current ECM pretesting depth: 17.812860
05/17/26 18:49:44, scheduled 35 curves at B1=11000 toward target pretesting depth of 20.000000
05/17/26 18:49:44, prp25 = 2204278978420309489529029
05/17/26 18:49:44, Total factoring time = 1.6291 seconds

Медленнее.
Но зато первый делитель нашёлся при B1=2e3 на 14 кривой из 30. А второй при B1=11e3 на 40 кривой из 74.

[wrest]

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

Видим что ECM нашёл один 17-значный делитель при B1=11e3 на четвёртой кривой из распланированных 45 (вместо 74), а при B1=2e3 все 30 кривых делителя не нашли.

А, ну похоже. Для rounds=4 и B1=11000 pari/gp тоже находит, за то же время:

? c=0;for(i=1,100,if(my_ecm(n,4,random(100),11000),c++));print(c)
100
time = 1min, 38,189 ms.
?

А вот при rounds=2 и B1=11000 уже процент удачи заметно меньше 100%

? c=0;for(i=1,100,if(my_ecm(n,2,random(100),11000),c++));print(c)
93
time = 1min, 17,920 ms.
?

[Dmitriy40]

Только YAFU в отличие от PARI умеет запускать ECM (как и SIQS и NFS) многопоточно, за что и нравится.

[wrest]

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

Только YAFU в отличие от PARI умеет запускать ECM (как и SIQS и NFS) многопоточно, за что и нравится.

Ну так многопоточно ECM и в pari можно, проблем вроде нет. Прерываться мы вроде раньше тут где-то научились.
Насчёт MPQS не уверен, надо внимательно смотреть, но наверное не получится, там же параллелится только первая стадия хорошо.
А NFS (GNFS) нам пока не надо, пишут что начинает лучше работать чем квадратичное решето от чисел длиной 100 цифр.

Ну вот судя по логам YAFU поднимается на этом числе по B1 выше (до 11000) чем pari/gp (до 2000), интересно почему такие решения приняли в pari. И как все-таки было бы правильном нам.
Тут нужна какая-то "настроенная" на равноделительную задачу таблица с B1 по которой идти, ну и таблица с rounds.

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

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

После нахождения делителя на 42 значное число натравили SIQS (другая разновидность QS вместо MPQS в PARI).

Тоже интересно - почему не ECM. Дальше мы видим почему:

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

Медленнее.

Но как принято решение...
Сперва имеем число длиной 194 бита с множителями 57+57+81 бит (но мы этого пока не знаем). Начали факторизовать. Нашли множитель 57 бит, 134 бита осталось. И теперь мы, наверное, думаем, что скорее всего там оба множителя примерно по 65..70 бит. Наверное какая-то такая логика.

[wrest]

Мы тут с Квеном прикинули, что вероятность того что наменьший делитель состоит из стольких-то десятичных цифр вот такая

P(p_min < z | N составное, B-грубое)
B=2^20, N=2^220, max log10(z) = 33.1

log10(z)   | P (точная)
-----------+----------------
         7 |          26.09%
         8 |          43.60%
         9 |          55.70%
        10 |          64.43%
        11 |          70.93%
        12 |          75.92%
        13 |          79.83%
        14 |          82.96%
        15 |          85.51%
        16 |          87.61%
        17 |          89.37%
        18 |          90.86%
        19 |          92.13%
        20 |          93.22%
        21 |          94.17%
        22 |          95.01%
        23 |          95.74%
        24 |          96.40%
        25 |          96.98%
        26 |          97.50%
        27 |          97.97%
        28 |          98.39%
        29 |          98.77%
        30 |          99.12%
        31 |          99.43%
        32 |          99.71%
        33 |          99.97%
time = 237 ms.
?

То есть, 80% чисел вокруг n=2^220, c учётом того что число точно составное и точно не содержит делителей меньше 2^20, будут содержать 14-значные и менее делители, а 90% -- 18-значные и менее.

Отсюда можно планировать, какими B1 в ECM делать проверки. Ну скажем, проверять такими что соотвестствуют 10^7, 10^9, 10^12, 10^18 и останавливаться на 10^20 (B1=11000), и дальше или переходить к mpqs или откладывать в долгий ящик. Осталось найти какие B1 каким делителям соответствуют.
В таблице Dmitriy40
topic161711-1170.html#p1724198 начинается с 20-значных, к сожалению.

[Dmitriy40]

Да, и ещё интересно что вероятность делителя меньше кубического корня аж 94%.

Вот поэтому и полезно быстро пройтись по всем местам с малым B1 (и rounds) в надежде что найдётся причина отбросить цепочку (например на месте pq останется составное частное или на месте pqr простое). Если не нашлась - увеличить B1 (или и rounds) и снова. И снова. Вплоть до B1 немного (раз в 10) больше чем для кубического корня.
Скорость проверки корректных цепочек (кортежей/ч) это даже замедлит, зато позволит быстрее перебирать кандидаты. Мне польза, Антону вред.

[wrest]

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

Да, и ещё интересно что вероятность делителя меньше кубического корня аж 94%.

Ну это надо ещё проверить.
Есть моя таблица "по 270 числам", там они в основном 10^55

Статистика по наименьшим простым множителям
10^6:1
10^7:10
10^8:14
10^9:17
10^10:25
10^11:23
10^12:23
10^13:19
10^14:23
10^15:19
10^16:11
10^17:6
10^18:10
10^19:11
10^20:2
10^21:8
10^22:16
10^23:4
10^24:3
10^25:6
10^26:9
10^27:5
10^28:4
10^29:1

Но не кумулятивная...
Там Yadryara похоже уже отрезал предыдущими фильтрациями (после пробноного деления) заметный кусок, т.к. с теорией совпадение плохое. Из 270 чисел, около 70 ожидаются с наименьшим делиоелем ~10^6..10^7 но в реальности (среди 270 чисел) такое число одно.

[Dmitriy40]

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

В таблице Dmitriy40
topic161711-1170.html#p1724198 начинается с 20-значных, к сожалению.

Для 15 значных используется B1=2000 и 30 кривых.
Для 10 значных видимо подойдёт B1=400-500 и 10 кривых.
Или взять формулу из PARI.
Вообще выбор B1 - довольно мутное дело.
Например на основе зависимости времени работы рекомендуют брать $B1=e^{\sqrt{\ln(p)\ln(\ln(p))/2}}$ (здесь $p$ - меньший простой делитель). В принципе она неплохо совпадает с таблицей.
Но только эти B1 - не для пары-тройки rounds/кривых, а для рекомендованного количества, которое десятки-сотни-тысячи.
И похоже скорость ECM для делителей до 15 цифр мало кого интересует - слишком она высока и так.

[wrest]

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

Но только эти B1 - не для пары-тройки rounds/кривых, а для рекомендованного количества, которое десятки-сотни-тысячи.

pari/gp не делает сотен итераций ECM. Только если запретить mpqs. Это ж неспроста :)
Ну в общем вот этот вот "тюнинг" перехода между ecm и mpqs может помочь немного ускорить факторизацию (в т.ч. финальную) в случае "равноделительной" задачи. Раза, может, в два.

[Yadryara]

Коллеги, я по-прежнему мало что понимаю в том что вы говорите, поэтому и помалкиваю.

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

Там Yadryara похоже уже отрезал предыдущими фильтрациями (после пробноного деления) заметный кусок, т.к. с теорией совпадение плохое. Из 270 чисел, около 70 ожидаются с наименьшим делиоелем ~10^6..10^7 но в реальности (среди 270 чисел) такое число одно.

Ну так я об этом прямо сказал. Ведь эти 270 чисел преодолели 9 фильтраций, а это не хухрёж-мухрёж. Причём, в общем случае, в программе обсчитываются варианты для частных не только с 4 и 8 делителями, но и с 16-ю.

И вот, кстати, серия 0-0-11-1, где одна 16-ка, пока показывает среднюю скорость нахождения около 100 в сутки, то есть явно выше 84-х. Досчитаю, покажу.

wrest, вы писали, что статистика должна быть ясной. А у вас она ясная?

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

Статистика по наименьшим простым множителям
10^6:1
10^7:10

Что такое "10^6:1" ? У меня вот написано чётко: n от 0 до 1eX.

И, мне пришлось ранее домысливать: я предположил что и у вас эта запись означает, что найден 1 фактор от 0 до 1е6.

А что, получается что имелась в виду верхняя граница на порядок выше? И не от нуля, а от 1е6 до 1е7 нашлась 1 штука, а от 1е7 до 1е8 — 10 штук?? Но восьмёрка-то вообще здесь не фигурирует.

Так что я совершенно не возражаю, чтобы статистика была ясной не только для того кто пишет.

[wrest]

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

А что, получается что имелась в виду верхняя граница на порядок выше? И не от нуля, а от 1е6 до 1е7 нашлась 1 штука,

Читать как
"шестизначных: один"
"семизначных: десять"
И так далее.
Эти гистограмма распределения наименьших делителей "270 чисел".
Видимо, после дофильтрации кундштюком, т.к. трёхзначных не видать.

[Yadryara]

Я так и читал. Но ведь вы вот что новое сказали:

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

Из 270 чисел, около 70 ожидаются с наименьшим делиоелем ~10^6..10^7 но в реальности (среди 270 чисел) такое число одно.

Как же одно, когда из вашей таблицы следует что 7-значных не одно, а 10 ??

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

Видимо, после дофильтрации кундштюком, т.к. трёхзначных не видать.

Ну конечно, ведь проверка по предпростым до 2^19-2 — это 6-я фильтрация.

После неё ещё три фильтрации были сделаны. Вот их можно ослаблять или ужесточать в тренировочном режиме и смотреть как влияет на скорость

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

Хотя с 7-й фильтрацией вроде ничего делать не надо, она по делу там стоит. Все частные с недобором проверяются на псевдопростоту и если вдруг хоть одно псевдопростое, то сразу вся цепочка отбрасывается.

[wrest]

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

Как же одно, когда из вашей таблицы следует что 7-значных не одно, а 10 ??

Ну значит таблица негодная.
Но вы же делаете статистику по наименьшим множителям по тем числам, факторизацию которых хотите (если всё ещё хотите) ускорить? Вот на неё и посмотрим.

[Yadryara]

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

И вот, кстати, серия 0-0-11-1, где одна 16-ка, пока показывает среднюю скорость нахождения около 100 в сутки, то есть явно выше 84-х. Досчитаю, покажу.

Скорость на тот момент достигла 103. И вот снизилась до 96. Более полная статистика по этой серии:

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

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

0-0-11-1   5!3!7!A!    120    17   1e68           0      568      4729          0
0-0-11-1   5!3!7!A!    120    18   1e68           0      512      4265          0

0-0-11-1   5!3!7!A!  21180    19   1e68         105    94713      4472         96
0-0-11-1   5!3!7!A!  16030    19   1e68          86    72042      4494        103
0-0-11-1   5!3!7!A!   6000    19   1e68          26    27153      4525         83
0-0-11-1   5!3!7!A!   2410    19   1e68           8    11083      4599         62
0-0-11-1   5!3!7!A!    120    19   1e68           0      504      4199          0

0-0-11-1   5!3!7!A!    120    20   1e68           0      523      4354          0

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

Скорость проверки корректных цепочек (кортежей/ч) это даже замедлит, зато позволит быстрее перебирать кандидаты. Мне польза, Антону вред.

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

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

В таблице уже довольно давно указываю среднее время счёта одного паттерна. Вот в этой таблице как раз видно, что я посмотрел средние времена счёта для одних и тех же паттернов при фильтрации по предпростым до 2 в степени 17, 18, 19 и 20. Они были такими 4729, 4265, 4199 и 4354 миллисекунд на паттерн соответственно.

Выбрал 19-ю степень и по ней уже считал дальше, пока 100 кортежей не нашлись.

[Yadryara]

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

Ну значит таблица негодная.

Ваша таблица? А в каком смысле негодная? В неё ошибка какая-то вкралась? Какая?

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

Но вы же делаете статистику по наименьшим множителям по тем числам, факторизацию которых хотите (если всё ещё хотите) ускорить?

Именно такую пока не делал. Но, если угодно, могу сделать. Много всякой статистики считаю и довольно много запланировано. Разумеется, желание ускорить никуда не делось.

Сейчас считаю так называемую скучную серию: 0-0-12-0.

Кстати, всё забываю спросить: теперь-то вы понимаете что мы считали, начиная с 14-й страницы? Сейчас это становится довольно актуально. И будет актуальнее для ещё бо́льших чисел.