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

[Dmitriy40]

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

Тут помог бы науерное parfor(), с выносом циклов факторизации в функцию.

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

export(ogrp); my(ste,t1,kol,kpod,n,fac,kunp,kdel,i);
parfor(ste=8,38,

Остальное остаётся как есть.

Правда при этом время будет печататься странно: оно будет близким у блоков длиной с количество потоков, просто за это время вычислится не одно ste, а сразу все сколько потоков. Итоговое же время будет правильным, оно однопоточно.
Многопоотчный вывод конечно нехорошо (и кстати нет гарантии что вывод п\будет подряд по ste), но вряд ли потоки будут заканчивать строго синхронно с точностью до миллисекунд (сколько занимает вывод строки). По хорошему надо строку возвращать как 4-й аргумент цикла parfor и печатать уже однопоточно в 5-м аргументе. Или не печатать, а сохранять в массив, а в конце печатать все до первой непосчитанной строки, так вывод будет подряд.

[Yadryara]

Спасибо, но я ни черта не понял И про нулевой фактор тоже.

[Dmitriy40]

Yadryara
А Вы точно хотели?

Заменить строку
for (ste = 8, 38,
в вашей программе на две строки
export(ogrp); my(ste,t1,kol,kpod,n,fac,kunp,kdel,i);
parfor(ste=8,38,
и запустить код под параллельной версией PARI/GP (gppthread64-2-17-3.exe) - и всё, делов-то.

А про нулевой фактор: перед вашей строкой
fac = factor(n); kunp = matsize(fac)[1];
добавить строку
if(factor(n,ogrp)[1,1]<ogrp, next);
и всё, будет более чем вдвое быстрее.

-- 24.11.2025, 19:28 --

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

-- 24.11.2025, 19:32 --

О, кстати сегодня новую версию PARI выложили. Важных исправлений не вижу, хотя sumnumrat() мы использовали в расчёте HL1, но особой точности там и не нужно.

[wrest]

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

Не поможет, слишком много накладных расходов. Параллелить надо самый внешний цикл,

Да, параллелить степени (по миллиону циклов), конечно.

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

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

Да, полностью согласен.

[Yadryara]

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

А про нулевой фактор: перед вашей строкой
fac = factor(n); kunp = matsize(fac)[1];
добавить строку
if(factor(n,ogrp)[1,1]<ogrp, next);

Благодарю. Сам хотел попробовать фактор с параметром и забыл уже. Но если есть нулевой, то может первый factor и не нужен... Может лучше попросту kdel=numdiv(n) ...

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

код под параллельной версией PARI/GP (gppthread64-2-17-3.exe)

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

Ещё можно по арифмосту как-то сориентироваться. Я иду пока только по нечётным, но вроде можно запретить остатки по всем простым модулям до 61 включительно.

Не, ну формул тогда будет немеряно. Золотую середину надо выбрать.

[wrest]

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

В убунте модифицированный код скорее всего (проверить не могу) сразу запустится параллельно,

Да, оно сразу многопоточное устанавливается по умолчанию.

-- 24.11.2025, 19:47 --

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

Может лучше попросту kdel=numdiv(n) ...

Не, почему-то оно так медленее, непонятно.

-- 24.11.2025, 20:02 --

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

Не, ну формул тогда будет немеряно. Золотую середину надо выбрать.

Золотая середина тут -- насколько вы цените время пока идёт счёт. Если хотите оптимизировать т.к. результаты нужны поскорее -- тратие ваше время на это. Или запускаете неоптимальный код, который считается то ли один то ли три часа - вам без разницы (особенно если на оптимизацию вы потратите час вашего времени, хотя могли бы заняться чем-то более важным).

[Yadryara]

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

Не, ну формул тогда будет немеряно. Золотую середину надо выбрать.

Хотя бы взять 8 формул по модулю 30. wrest, понимаете о чём я?

[wrest]

Yadryara
В этом вашем коде всё, кроме основной факторизации, примерно полсекунды-секунда на миллион проверок (где-то 200мс на собственно организацию цикла, присваивание туда-сюда, простые вычисления).

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

-- 24.11.2025, 20:11 --

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

Хотя бы взять 8 формул по модулю 30. wrest, понимаете о чём я?

Нет, но возьмите и попробуйте.

[Yadryara]

wrest, на самом деле желательно посчитать где-то до 52-й степени 10-ки.

Но я хочу обратить Ваше внимание именно на метод. Вы заметили что перебор идёт только по нечётным числам? Понятно же почему, не правда ли. Ну а на 5-ку может заканчиваться кандидат? Да нет конечно, такие и проверять бесполезно. А какие ещё можно не проверять? Ну вот 22 числа из каждых 30-ти можно не проверять.

Достаточно проверять 8 из 30. Что же 56 из 210 ? Нет, достаточно проверять 48 из 210. А на самом деле — ещё меньше. И можно вначале быстренько составить список по праймориальному модулю и шагать по нему.

[Dmitriy40]

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

И можно вначале быстренько составить список по праймориальному модулю и шагать по нему.

Даже для 13# я никакого заметного ускорения не вижу. А для 17# наоборот замедление.
Видимо factor(n,67) работает достаточно быстро чтобы уменьшение количества его вызовов роли не играло.

-- 24.11.2025, 21:18 --

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

желательно посчитать где-то до 52-й степени 10-ки.

10^33:   131580       101   282   322   198        5min, 49,258 ms
10^34:   131571       96   278   319   202        7min, 6,105 ms
10^35:   131600       94   272   319   205        8min, 35,925 ms
10^36:   131596       92   266   321   207        10min, 44,966 ms
10^37:   131589       89   262   319   212        12min, 45,356 ms
10^38:   131601       88   258   316   213        15min, 27,871 ms
10^39:   131582       86   254   314   216        33min, 6,522 ms
10^40:   131600       83   250   312   218        38min, 53,482 ms
10^41:   131593       80   244   315   219        1h, 3min, 48,726 ms
10^42:   131577       77   244   312   224        1h, 10min, 8,913 ms
10^43:   131565       77   236   309   227        1h, 24min, 11,953 ms
10^44:   131564       74   234   307   228        1h, 36min, 56,354 ms
10^45:   131590       73   232   305   230        2h, 28min, 31,142 ms
10^46:   131585       72   229   302   231        2h, 30min, 34,431 ms

Начиная с 39-й степени считалось в 4 потока в фоне. Жаль оборвал, скоро могли быть и 47 и 48.

[wrest]

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

Но я хочу обратить Ваше внимание именно на метод. Вы заметили что перебор идёт только по нечётным числам? Понятно же почему, не правда ли. Ну а на 5-ку может заканчиваться кандидат? Да нет конечно, такие и проверять бесполезно. А какие ещё можно не проверять? Ну вот 22 числа из каждых 30-ти можно не проверять.

Достаточно проверять 8 из 30. Что же 56 из 210 ? Нет, достаточно проверять 48 из 210. А на самом деле — ещё меньше. И можно вначале быстренько составить список по праймориальному модулю и шагать по нему.

Всё это относится к математической части оптимизации. Вы же привели пример когда компиляция замедлила исполнение, а это другая опера.

-- 24.11.2025, 21:29 --

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

Видимо factor(n,67) работает достаточно быстро чтобы уменьшение количества его вызовов роли не играло.

Очень быстро

? for(i=10^15,10^15+10^6, f=factor(i))
time = 13,833 ms.
? for(i=10^15,10^15+10^6, f=factor(i,67))
time = 629 ms.
? for(i=10^15,10^15+10^6, f=i%67)
time = 205 ms.
?

[Dmitriy40]

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

Очень быстро

Тут надо сравнить сколько в % чисел будет отброшено и дальше не пройдёт - вот такую долю и можно выиграть заменой factor(n,67) на таблицу правильных остатков по модулю 67# (в память и на диск не влезет).
Но я значимого ускорения не вижу. А с ростом таблиц начинается замедление (обращение к большой таблице не бесплатное).
А ещё можно factor(n,67)[1,1]<=67 заменить на gcd(n,67#)>1, но думаю заметного ускорения тоже не будет.

[Yadryara]

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

Даже для 13# я никакого заметного ускорения не вижу.

А я говорил пока про 5# и 7#. Для них видите?

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

Жаль оборвал, скоро могли быть и 47 и 48.

Да, это же расчёт частотности о которой писал VAL. Только уже конкретный.

И, как видим, примерно на 1e46 состоялся обгон. То есть в терминологии Владимира, pqrs стали встречаться чаще чем pq.

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

это другая опера.

Чтобы писать быстрые программы, надо не только "Лебединое" смотреть, но и "Щелкунчика" не прощёлкать.

Часов через 5-6 у меня счёт закончится, буду дальше скорость засекать.

[Yadryara]

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

Тут надо сравнить сколько в % чисел будет отброшено и дальше не пройдёт

Это кстати во втором столбце показано: остаётся не более 13.2 % чисел.

[Dmitriy40]

Продолжение таблицы (в 4 потока):

10^47:   131595       72   223   301   233        3h, 25min, 19,982 ms
10^48:   131571       68   221   300   236        4h, 53min, 47,035 ms
10^49:   131576       68   220   298   235        5h, 20min, 41,045 ms
10^50:   131574       67   217   296   236        6h, 41min, 49,942 ms

После чего программа вылетела по нехватке памяти для parfor (интересно какого фига?!).

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

А я говорил пока про 5# и 7#. Для них видите?

Тем более нет.

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

А ещё можно factor(n,67)[1,1]<=67 заменить на gcd(n,67#)>1, но думаю заметного ускорения тоже не будет.

Да, нету, скорость та же с точностью до случайных флуктуаций.