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

[wrest]

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

2c. omega_upto on ubuntu after compile
3c. omega_range on ubuntu after compile

Эти функции "встроенные" теперь. Но скрипт, который их использует, пока транслировать при помощи gp2c в Си и затем скомпилировать нельзя или затруднено (не уверен, надо разбираться). То есть функции скорее как proof of concept. Если "зайдут" можно будет подумать об э... "полной встройке", чтобы не надо было делать install. Но там вылезает, видимо, вопрос поддержки многопоточности, для меня terra incognita.

[Yadryara]

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

И про какой из них речь вообще непонятно.

Самый быстрый вот этот:

4c. forprime on ubuntu after compile

И параллельный счёт пока прекрасный. Если в два потока он считал за 41 минуту юнит, то в 9 потоков за 55 минут.

И памяти пока хватает: по 32-64 МБ на поток.

removeprimes(addprimes()); пока в программе остаётся.

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

[Dmitriy40]

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

Появляется 580... , но исчезает 1294...

580... появляется потому что в ней стоит лишняя 41 (она оказывается в кубе вместо квадрата) на 6-й позиции, factor это обнаруживает, forprime нет.
С 1294... наоборот, там на 1-й позиции 97^2, factor это видит и оставляет в частном простое, forprime (почему-то без модификации отбрасывания квадратов и меньшего требуемого количества делителей) квадрата не видит и оставляет в частном составное, которое и является причиной отбросить кандидата. С добавкой проверки квадратов она отбрасывается и forprime тоже.
Итого, всё работает правильно, но (в недоработанном виде) не так как желается.

-- 04.12.2025, 17:17 --

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

Самый быстрый вот этот:
4c. forprime on ubuntu after compile

Почему в нём не вот этот вариант проверки используется? Ведь он фильтрует в сотню раз лучше.

[Yadryara]

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

Итого, всё работает правильно, но (в недоработанном виде) не так как желается.

То есть решение всё-таки может быть пропущено, хотя и с крошечной вероятностью?

-- 04.12.2025, 17:32 --

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

Почему в нём не вот этот вариант
проверки используется? Ведь он фильтрует в сотню раз лучше.

Не понял вопроса. Я фильтрую по предложенному Вами варианту с forprime, который по тесту самый быстрый. От factоr-а пока отказался.

Про сотню раз очень сомнительно.

Я бы скинул рабочую программу, но там столько всего ещё чистить...

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

Пошёл пока в старый 2.15.4

Это какая-то фантастика:

1000000/189   1min, 32,875 ms
1000000/200         14,550 ms

Здесь я имел в виду что после компиляции прога с фактором замедлилась в три раза, а прога с forprime наоборот ускорилась в три раза. И в итоге в 6 раз быстрее работала.

[Dmitriy40]

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

Но там вылезает, видимо, вопрос поддержки многопоточности, для меня terra incognita.

В PARI многопоточность ... э ... кривоватая странная, даже на системах с общей памятью он считает что память раздельная (локальная) и дублирует даже read only данные в каждый поток. В данном случае кроме действительно локальных переменных будет дублирована и вся таблица простых для forprime ... Это и память и время на копирование.
Возможно стоит подумать об своей таблице простых, тем более что их можно хранить намного компактнее (например всего 137МБ до 2^32 вместо 10ГБ у PARI). Хотя возможно придётся общую таблицу разбить на две, с прямым видом для простых до скажем пары тысяч (ради скорости перебора) и компактным видом для всех остальных, тут уже скорость доступа меньше тормозит.

-- 04.12.2025, 17:44 --

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

То есть решение всё-таки может быть пропущено, хотя и с крошечной вероятностью?

Нет, Вы разве не видели что написал про квадрат и куб? Они решениями нами пока не считаются.

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

Не понял вопроса. Я фильтрую по предложенному Вами варианту с forprime, который по тесту самый быстрый. От factоr-а пока отказался.

Ещё раз прочитайте сообщение по ссылке. Там приведён доработанный код! Который отфильтровывает и квадраты и numdiv<48. В Вашем же списке они есть - значит у Вас код старый, не доработанный. В этом и вопрос - почему. Потому что с доработанным должно быть не 100000/19, а 100000/1 (и 1000000/1).

-- 04.12.2025, 18:00 --

Для информации: проверка простых 3...19 что они в правильной степени (это "длинный" if в программах VAL), отфильтровывает 5.85:1, проверка и простых 23...53 что они в квадратах (цикл с T[],P[] в программах VAL) улучшает фильтрацию до 7.35:1, но к сожалению несколько увеличивает время выполнения, для 1млн кандидатов с 44.9с до 48.4с.
Правда это если скорость оценивать по уже пофильтрованным кандидатам. Если же оценивать по диапазону i (или n что эквивалентно), как и должно быть, то второй вариант быстрее процентов на 15: 5847153/44.9 > 7348061/48.4.

[Yadryara]

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

Если в два потока он считал за 41 минуту юнит, то в 9 потоков за 55 минут.

Ага, вот и плохая новость. В 12 потоков уже резкое замедление: по 73-74 минуты на юнит. Значит пока не буду считать в 12.

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

Там приведён доработанный код!

Да, действительно не заметил. Сейчас буду разбираться.

[Yadryara]

Разобрался. Вроде в 3-5 раз лучше фильтрует. Всё равно много остаётся. Так что фильтрация выше $2^{20}$ всё равно нужна. А по скорости доработанная показывает примерно то же самое.

Хотя нет, всё же побыстрее: 39 минут, но это 6 потоков.

[wrest]

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

замените на вот эти:

Сдаётся мне, что вот эти две проверки лишние:

Используется синтаксис C

      if(nf[d]>nu[d], next(2));\\Если уже перебор, то отбрасываем
      if(x%p^2<#v, next(2));\\Проверка на степени выше первой, такие n сразу отбрасываем

Превышения по количеству множителей быть не может т.к. мы следующей проверкой после этих двух проверяем равенство и до перебора не доходит.
Выключение проверки на бесквадратность не меняет результат - несвободные от квадратов отсекаются другими проверками. Возможно это особенность конкретного набора/шаблона.

[Dmitriy40]

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

Разобрался. Вроде в 3-5 раз лучше фильтрует. Всё равно много остаётся.

А у меня в 160 раз: вместо 10млн:2076 остаётся 10млн:13. И я уже не думаю что 13 штук за несколько минут это "много".
Но никто же не мешает поставить и 2^21 в forprime и сравнить сколько останется и скорость. Правда тогда лучше бы повысить и default(primelimit,2^21) в начале программы, чтобы встроенная таблица простых тоже стала 2^21, а то forprime будет каждый раз заново искать простые 2^20...2^21.

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

Превышения по количеству множителей быть не может т.к. мы следующей проверкой после этих двух проверяем равенство и до перебора не доходит.

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

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

Выключение проверки на бесквадратность не меняет результат - несвободные от кваратов отсекаются другими проверками. Возможно это особенность конкретного набора/шаблона.

Зато проверка на квадрат намного быстрее ispseudoprime, на 1млн её добавление даёт 3% ускорения. А уж после компиляции должно быть и ещё лучше.

[Yadryara]

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

А у меня в 160 раз: вместо 10млн:2076 остаётся 10млн:13. И я уже не думаю что 13 штук за несколько минут это "много".

Всё руки не дойдут вернуться к Вашей тестовой проге и сделать нормальную проверку. У меня ведь пока ещё две проверки работают, самые примитивные:

for(nom = 1, #pq,   if(numdiv(n+pq[nom]-1)   <> kdel, next(2)));
for(nom = 1, #pqrs, if(numdiv(n+pqrs[nom]-1) <> kdel, next(2)));

А kdel = 48.

И вот только после этих проверок наконец-то остаётся комфортное количество приближений: около 180 за 5 часов в 9 потоков.

Сколько подаётся кандидатов на вход я пока не смотрел. И ещё: у Вас паттерн заточен под 0 простых, а у меня под 1 простое.

Понятно, что fаctor скорее всего и здесь сработает быстрее чем numdiv. Но пока не переделывал.

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

Правда тогда лучше бы повысить и default(primelimit,2^21) в начале программы,

Я так понимаю, что так же как и allocatemem, эту команду нужно давать ещё до компиляции, то есть она вообще не в программе должна быть.

И я уже пытался раньше повысить порог простых выше 2^20, но на скорость это не повлияло. Не помню какую давал команду, но primelimit увеличивался. Кстати сейчас только обратил внимание: в версии 2.15.4 у меня primelimit=500000.

[wrest]

Немного статистики.
Запускаю генерацию n вот так:

Используется синтаксис C

n0=283938699868309713921641266159023371777169;
m=229403502054304075118105309394590566946400;
for(lim=9,20,q=0; t0=getwalltime();
  for(i=1,1000000,
     n=n0+m*i*2;
     q+=checkD48_21(n,2^lim);
     );
   print("lim=",2^lim," passed=",q, " time: ",strtime(getwalltime()-t0));
   );

Проверок "такие нам не нужны не делаю".
Функция checkD48_21(n,2^lim);- проверяет способом forprime(59,lim ....)
Результат такой. Интерпретация:
lim=512 passed=11007 time: 27,136 ms
lim=1024 passed=4068 time: 26,546 ms
lim=2048 passed=1510 time: 24,978 ms
lim=4096 passed=542 time: 25,053 ms
lim=8192 passed=228 time: 25,473 ms
lim=16384 passed=102 time: 27,477 ms
lim=32768 passed=40 time: 27,170 ms
lim=65536 passed=19 time: 28,314 ms
lim=131072 passed=11 time: 29,373 ms
lim=262144 passed=5 time: 30,858 ms
lim=524288 passed=3 time: 32,138 ms
lim=1048576 passed=2 time: 43,510 ms
Надо осмыслить
Ещё появились кое-какие мысли, но надо потестить.

-- 05.12.2025, 02:18 --

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

Я так понимаю, что так же как и allocatemem, эту команду нужно давать ещё до компиляции, то есть она вообще не в программе должна быть.

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

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

Сейчас эта таблица содержит простые не превышающие 2^20, так что вам надо запускать pari с установкой нужного вам primelimit
при primelemit=2^32 таблица займёт 10 гигабайт памяти!
Почитайте про primelimit тут: https://pari.math.u-bordeaux.fr/dochtml ... aults.html

[Yadryara]

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

Это нужно делать до запуска интерпретатора.

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

[Dmitriy40]

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

Функция checkD48_21(n,2^lim);- проверяет способом forprime(59,lim ....)

А v[] и nu[] не используются что ли? Тогда это не слишком корректно, в n+d же куча малых делителей (собранных в v[]), которые не дадут частному стать простым в ispseudoprime. Или эти массивы в самой функции?

-- 05.12.2025, 02:45 --

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

Надо осмыслить

Судя по данным ставить порог выше 2^18 нет смысла, несколько штук проще допроверить прямым numdiv/factor.

[Yadryara]

Кстати, поясню что такое комфортное количество приближений. Это когда их не слишком много и не слишком мало. Например, сейчас уже не слишком комфортно: не в каждом потоке они помещаются на экран. Вот часть того что я вижу при работе программы:

Potok 8


59.   [11, 22, 2, 19]

6477170347906465930690546606043292674855920413570841             11 1 11 111 111111 1        15
4680745276339047994095480858765297957317085375398041        1    1 111 111 1 11 111          14
5419111937602662567021399797849473104799173174090841             111  111  1 1111111111      17
5039370046121347124972606170446883460172931371758041              11 11111111111111 111      19
4926307585389952809599608254011996479819295469916441               1 1 111  111 1111  1      13
8634627117447906702975479326343374599900996010862041             11 11 1 11 11 111111 1      16
4333091735402087079477146869400089561217889037492441        1    1 11 111 11 11111111        17
6611616445490321593562948905393195379055834100156441               1   11111 1  111 1 1      12
6903165007508179026404087045526107815776970060799641              1 11111  1 1 11111 1       14
6906537662131863285045439930408150418113337532258841        1    1 1 1111   111 11111 1      16
3742964670948424160341302436634817451668241977791641             11 1  11 11 11111111        15
3789324577933878571738422100969423862687299883111641              11   1 11111 11111 1       14
3917009971788523595894388788115838349120603225644441              1    1 11  1 111111 1      12
4512301057392841263010951073112933896947033227868441             11111 11111 1111111111      20
3348808098429699131275009652107378524751324578863641             11  1111  1 1 11111111      16

Здесь предпоследняя — одна из двух найденных за 6 часов цепочек с valids=20.

[wrest]

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

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

Ну вы же запускаете pari/gp
Вот он должен запускаться с нужным вам primelimit, то есть вот тут вы его должны видеть:

Type ? for help, \q to quit.
Type ?18 for how to get moral (and possibly technical) support.

parisizemax = 2000003072, [b]primelimit = 1048576[/b], factorlimit = 1048576

для этого надо править файл настроек gprc
Заодно и parisizemax поднимите.