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

[wrest]

Я тут подумал, что когда/если наладите parfor, то и эту фильтрацию

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

3-я фильтрация: проверка всей цепочки по предпростым до $2^{20}$, сбор факторов

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

[Yadryara]

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

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

Вот это соображение говорит против parfor-а. То есть если проверяемые числа (частные) в одной и той же цепочке порой отличаются на 5-6 порядков, то их вроде быстрее проверять именно последовательно, а не параллельно.

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

Я, пока игрался с ним, до сильно больших чисел не дошёл, но вот раскладка по числу 299381200402498733 :

[1, 220, 9973, 30019171804121]   6 ms
[2,  12, 9973, 30019171804121]   1 ms

Первое число это константа c, второе — количество итераций до успеха, далее фактор и кофактор.

То есть cчёт занимает сильно разное время в зависимости от удачи в выборе константы.

-- 12.03.2026, 13:41 --

Ну или вот для актуального числа:

[ 1, 3143, 15621763, 614813194568884725330347254101670326647553073]   9 ms
[11,  942, 15621763, 614813194568884725330347254101670326647553073]   4 ms

[Yadryara]

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

Я пока грешу на алгоритм Полларда.

Да, это из-за него память так тратилась. Я же ведь делал не сам, взял функцию, которую Квен наваял. А теперь на глазок поставил ограничение в 20 констант и 10 тысяч итераций. Вроде ошибок пока нет.

[Dmitriy40]

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

Вот это соображение говорит против parfor-а. То есть если проверяемые числа (частные) в одной и той же цепочке порой отличаются на 5-6 порядков, то их вроде быстрее проверять именно последовательно, а не параллельно.

Я этого не понял.
Если наименьшее число самое трудно факторизуемое (оба делителя большие), то очевидно проверять лучше не в порядке возрастания.
При этом параллельный вариант проверяет числа до первого "неуспеха", т.е. до самого лёгкого числа, независимо от его позиции в любом списке (хоть сортированном, хоть нет).
Ну и как это можно обогнать? Только если затраты на организацию параллельности превысят время факторизации первых чисел. Но мы же не можем отсортировать числа в порядке лёгкости факторизации - наименьшее полупростое наверняка окажется труднее чем большее но из 3-4 факторов. Т.е. хоть корреляция между величиной чисел и лёгкостью факторизации и есть, но она не настолько сильна чтобы переломить выгоду от параллельности (которая проверяет лишь до самого легкого числа из всех запущенных).

И да, PARI может запустить потоков больше чем есть в наличии ядер - просто ставим нужное значение nbthreads и всё, хоть 100500.

[wrest]

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

Я же ведь делал не сам, взял функцию, которую Квен наваял.

Есть же встроенная

Цитата:

GEN Z_pollardbrent(GEN N, long n, long seed) try to factor t_INT N using n ≥ 1 rounds of Pollard iterations; seed is an integer whose value (mod 8) selects the quadratic polynomial use to generate Pollard’s (pseudo)random walk. Returns NULL on failure, else a vector of 2 (possibly 3) integers whose product is N.

Устанавливается так:
install(Z_pollardbrent,GLL)
Запускаем:

? Z_pollardbrent(15621763*614813194568884725330347254101670326647553073,10^2,1)
time = 3 ms.
%4 = [15621763, 614813194568884725330347254101670326647553073]
?

-- 12.03.2026, 15:53 --

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

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

Тут вопрос опять насчёт "обогнать".
Допустим у нас 8 потоков и времена однопоточного разложения такие:
1000, 100, 200, 200, 300, 300, 500, 700
Тогда, установив таймер на 150, мы затратим 250 (на 150 прервется первое и второе использует 100). Причем это 250 одного потока (realtime), соответственно в сумме тоже 250 (cpu time).
Параллельно мы затратим 100 абсолютного (realtime), но 100*8=800 (cpu time) суммарного.

[Dmitriy40]

wrest
А мы оптимизируем realtime или cpu time?
Если программ много, то cpu time (и тогда непонятно зачем вообще параллельность в самой программе), но если она одна, то realtime (именно его мы тратим до получения решения).
А наша одна с parfor загрузит все ядра практически на 100% и нет смысла запускать несколько программ.

-- 12.03.2026, 16:15 --

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

Допустим у нас 8 потоков и времена однопоточного разложения такие:
1000, 100, 200, 200, 300, 300, 500, 700

И вероятность такого случая достаточно мала и соответственно в общем времени перебора миллионов чисел существенно на общее время не повлияет - посчитайте общее время перебора всех 8! вариантов перетасовок этих времён. А параллельность на parfor - ещё как повлияет, потому что все 8! вариантов выполнятся за 100мс realtime каждый.

-- 12.03.2026, 16:21 --

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

посчитайте общее время перебора всех 8! вариантов перетасовок этих времён

У меня получилось 25200000 с таймером на 150 против 4032000 параллельно, в 6.25 раз больше. Т.е. с parfor результат будет получен в среднем вшестеро быстрее (по часам реального времени).

[Yadryara]

Господа, попозже отвечу. Ошибку важней было отследить. Это не ошибка в программе, это забывчивость. Степени старше 1-й редко встречаются, но встречаются же.

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

Откуда тут 2-значный фактор взялся, если все факторы должны быть больше $2^{20}$, то бишь не менее чем 7-значными, это ведь проверяется раньше.

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

[wrest]

Yadryara
Вообще, похоже пришла пора открыть вам новые тайны pari/gp
Вот тут https://pari.math.u-bordeaux.fr/pub/par ... ibpari.pdf описываются функции в библиотеке pari, которые "светятся" из ядра, но не для всех них есть встроенные в интерпретаторе.
Факторизация там начирая со стр. 174
Обычно вы можете установить библиотечную функцию и использовать её как встроенную через install()
Поскольку у них там свой подход к именованию, то install() позволяет вам установить функцию под другим именем, например Z_pollardbrent() можно установить как plrd():

install(Z_pollardbrent,GLL,plrd)

-- 12.03.2026, 16:30 --

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

А наша одна с parfor загрузит все ядра практически на 100% и нет смысла запускать несколько программ.

Ну на время исполнения parfor-а да, загрузит, а остальное-то идёт в основном последовательно. Вот это последовательное пусть идёт параллельно в разных сессиях например. Я бы вообще и разные "комплекты" parfor-ом запускал но для этого надо переделать код в функциию а Yadryara не хочет

-- 12.03.2026, 16:34 --

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

У меня получилось 25200000 с таймером на 150 против 4032000 параллельно, в 6.25 раз больше. Т.е. с parfor результат будет получен в среднем вшестеро быстрее (по часам реального времени).

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

[Dmitriy40]

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

но для этого надо переделать код в функциию

Не надо, любой for заменяем на parfor и долго мучаемся с глобальными переменными.

[Yadryara]

У меня из-за склейки через 59 минут сообщение исчезло. Тогда в этот пост сразу два вставлю.

Господа, попозже отвечу. Ошибку важней было отследить. Это не ошибка в программе, это забывчивость. Степени старше 1-й редко встречаются, но встречаются же.

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

Откуда тут 2-значный фактор взялся, если все факторы должны быть больше $2^{20}$, то бишь не менее чем 7-значными, это ведь проверяется раньше.

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

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

ограничение в 20 констант и 10 тысяч итераций.

Сделал 21 и 4 тысячи. Пока добился общего времени не 117 и не 104, а всего лишь 82 секунды.

(Оффтоп)

   Мест           Время  Конс     Итер    Длина  Длина
пров. прев.             танта     аций  фактора  пров.
10        2        5 ms     1     3143        8     52
5         1        7 ms     2     2644        8     47
7         1        2 ms     1     1823        7     53
9         1        8 ms     2     3297        9     51
6         2      102 ms     1     1838        7     52
8         1        9 ms     2     3435       10     52
12        4      212 ms     3     2826        8     46
5         2      109 ms     2     3444        8     52
7         1        3 ms     1     2705        7     50
11        3      206 ms     2     1737        8     54
8         1       57 ms    12     3502        9     53
7         1        8 ms     2     2785        8     53
9         4      217 ms     1     3485        8     49
5         5      310 ms     1     3758        8     51
5         2        4 ms     1      487        7     47
9         6      292 ms     1      737        7     52
8         2      103 ms     1     2543        8     52
6         1        5 ms     1     3912        9     52
8         2        6 ms     1     1950        7     49
10        7      672 ms    21     1971        9     52
10        2      101 ms     1      462        7     48
8         8      472 ms     1     3904        7     51
9         1        3 ms     1     2245        7     50
4         4      195 ms     1      930        7     51
6         1       13 ms     3     2586        8     48
5         2      101 ms     1     2350        8     44
10        1        3 ms     1     2412        8     50
7         4      214 ms     1     1592        7     51
6         5      322 ms     3     3605        9     46
7         4      299 ms     1     2880        7     52
7         2        4 ms     1     2808        7     45
5         2      124 ms     6     2178        8     51
7         1        2 ms     1     1879        8     51
7         3      194 ms     1     3403        8     51
6         1        0 ms     1      336        7     47
8         1       12 ms     3     2825        8     51
11        5      200 ms     1     1435        7     52
6         1       72 ms    16     1588        9     50
10        2      110 ms     3     3676        8     47
3         1        2 ms     1     1038        7     51
10        2       17 ms     3     3068        9     47
8         2      100 ms     1     1959        8     49
11        3      197 ms     1     2748        7     45
9         4      213 ms     1     1868        7     53
10        3      110 ms     2     2585        7     48
9         2      124 ms     6     2932        8     49
7         7      483 ms     7     2125        8     49
9         2       98 ms     1      777        7     51
8         3      195 ms     1        4        2     53
8         4      204 ms     1     1114        7     52
9         1        2 ms     1     1746        7     52
7         3      146 ms    10     1416        9     48
7         2       97 ms     1      322        7     50

1min, 21,748 ms

Ещё не все идеи ускорения реализованы.

Но вот под конец ошибка вылезла. Откуда тут 2-значный фактор взялся, если все факторы должны быть больше $2^{20}$, то бишь не менее чем 7-значными, это ведь проверяется раньше.

Комент по этому поводу выше.

Да, и забыл сказать: показаны 53 цепочки из 57, которые добрались до 6-й фильтрации. Ещё 4 были отброшены в результате 7-й, пока последней фильтрации.

-- 12.03.2026, 17:39 --

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

Если наименьшее число самое трудно факторизуемое (оба делителя большие), то очевидно проверять лучше не в порядке возрастания.

Смотря что считать большим делителем. Неужто 7-значные факторы считаете большими?

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

Ну и как это можно обогнать?

Посмотрим что скажут тесты. Я пока ещё не сделал сортировку.

[wrest]

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

Не надо, любой for заменяем на parfor и долго мучаемся с глобальными переменными.

Ну дык кто ж заставит-то красиво делать мучайтесь, раз видите другие плюсы

-- 12.03.2026, 18:05 --

Yadryara
Если будете пробовать встроенный Поллард-Брент ро

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

Устанавливается так:
install(Z_pollardbrent,GLL)
Запускаем:
Код:
? Z_pollardbrent(15621763*614813194568884725330347254101670326647553073,10^2,1)
time = 3 ms.
%4 = [15621763, 614813194568884725330347254101670326647553073]
?

то есть такая особенность. Интерпретатор, если какая-то функция возвращает NULL, выпадает в ошибку.
Чтобы этого не происходило, нужна вспомогательная функция
isNULL(x=0)=x
И запускать через неё, т.е.

? isNULL(Z_pollardbrent(9604466014828004353430781511277071747020658636327699,10,1))
time = 1 ms.
%41 = 0
?

Тут 10 итераций не хватило, поэтому Z_pollardbrent возвращает NULL, а isNULL() конвертирует NULL уже обычный 0 (ноль).
Ну или объявить ещё одну, уже обёрнутую функцию, например

? isNULL(x=0)=x;
? my_pollard(n,iter,seed)=isNULL(Z_pollardbrent(n,iter,seed));
?

10 итераций мало, возвращаем ноль:

? my_pollard(9604466014828004353430781511277071747020658636327699,10,1)
time = 1 ms.
%56 = 0
?

50 итераций хватило, возвращаем два делителя множителя:

? my_pollard(9604466014828004353430781511277071747020658636327699,50,1)
time = 5 ms.
%57 = [15621763, 614813194568884725330347254101670326647553073]
?

[Dmitriy40]

А чем Поллард быстрее ECM? Точнее чем factor?
Тем более что factor/factorint использует и Полларда тоже?

[wrest]

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

А чем Поллард быстрее ECM?

Ну алгоритм простой. Он ищет один небольшой множитель и останавливается. Это быстро и удобно. Если все множители большие, то работает долго, потому и таймер нужен. А если есть один небольшой, то работает весьма быстро. Когда найден один [простой] множитель а нам не хватает два, то проверяем остаток (частное) на псевдопростоту (быстро) и вуаля.

? my_pollard(9604466014828004353430781511277071747020658636327699,50,1)
time = 3 ms.
%72 = [15621763, 614813194568884725330347254101670326647553073]
? factor(9604466014828004353430781511277071747020658636327699)
time = 124 ms.
%73 =
[               15621763 1]

[16792084195298082608383 1]

[36613274887046916980431 1]

?

3мс vs 120мс
Но вот остаток (частное) от первого полларда 614813194568884725330347254101670326647553073 следующим поллардом уже не развалить на два т.к. множители большие: 16792084195298082608383 и 36613274887046916980431 .

-- 12.03.2026, 20:51 --

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

Тем более что factor/factorint использует и Полларда тоже?

Ими труднее управлять в плане остановки после нахождения первого множителя или нужного их количества. Для этого я как раз и делал для Yadryara функцию встроенную в ядро omega_upto() К моменту проверки поллардом, число уже проверено по таблице простых до $2^{20}$, и как эту проверку пропустить в "стандартном" factor/factorint -- неясно.
И вот как раз на следующем этапе, когда ясно что остались только большие множители, можно сразу запускать ECM.

[Dmitriy40]

wrest
Так вот и сравните скорость Полларда и omega_upto (или её модификации для одного делителя) для поиска лишь одного делителя (не обязательно наименьшего, просто одного).
И лучше бы меньший делитель взять побольше, чтобы любые алгоритмы работали хотя бы сотни мс (а лучше секунды). Например 2879523051068277987785673526992445671701886820473042076988851.

[wrest]

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

Так вот и сравните скорость Полларда и omega_upto

Это муторно, может попозже - я ж с планшета в основном флужу, а omega_upto где-то в ноуте...

? my_pollard(2879523051068277987785673526992445671701886820473042076988851,10^4,1)
time = 147 ms.
%22 = 0
? factor(2879523051068277987785673526992445671701886820473042076988851)
time = 516 ms.
%23 =
[       4683573931895587 1]

[16792084195298082608383 1]

[36613274887046916980431 1]

?

поллард быстрее factor-a