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

[Yadryara]

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

Я понял так: у вас запущено четыре окна с сессиями WSL с Ubuntu, во всех окнах работает pari/gp,

Да.

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

в трёх окнах в pari/gp работает какой-то for(),

Нет просто множитель при потоке указан. Это в самом верху .gp-файла:

/*
GP;default(parisizemax, 2^27);
GP;init_Rab_113_118_1();
*/

{t0=getwalltime();print;

potok = 0;

А в двух других окнах potok = 7; и potok = 8; соответственно.

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

а в четвёртом работает parfor(i=1,6,...

Здесь вот так:

/*
GP;default(threadsize,128M);
GP;default(debugmem,0);
GP;init_Rab_113_118_2();
*/

funall ( potok:small ) = {

t0=getwalltime();print;

И уже в самом низу:

return(k48);
}

{parfor(potok = 1, 6, funall(potok));

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

Или необязательно, чтоб функция хоть что-то возвращала?

[Yadryara]

Ну вот так-то. Юниты в отдельных окнах посчитались быстрее. Не сильно, но быстрее. 455 минут против 465. Буду ещё отдельно запускать 12 потоков в одном окне.

[wrest]

Yadryara
Советую убедиться, что время считается верно, т.е. проследить как меняется переменная t0.
В функции em3 с 29-й страницы переменная t0 объявлена как локальная
my(t0=getwalltime());
Соответственно глобальная переменная с именем t0 если и есть, то не изменяется внутри функции em3.

[Yadryara]

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

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

Я смотрел по времени записи в лог. Старт многопоточной программы был в 21:37 и к новому юниту она перешла в 5:22. Старт очередного юнита в потоке 8 был в 21:46 и к новому юниту он перешёл в 5:21. То есть опережение на 10 минут.

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

Соответственно глобальная переменная с именем t0 если и есть, то не изменяется внутри функции em3.

Да, в курсе. Но я здесь не использовал функцию em3, а объявил грубо говоря, всю программу funall.

[wrest]

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

Но я здесь не использовал функцию em3, а объявил грубо говоря, всю программу funall.

Я поэтому и посоветовал убедиться, т.к. в параллельном цикле вы вызываете funall
parfor(potok = 1, 6, funall(potok));
А в funall переменная t0 не объявлена через my() как локальная.
funall ( potok:small ) = {

t0=getwalltime();print;
Поскольку вы смотрите на абсолютное время, то всё Ок.

[Yadryara]

Сделал-таки короткую арифметику хоть в каком-то виде. У меня программа сейчас работает на 12% быстрее.

Далеко не в 5 раз быстрее. Полагаю, это из-за того, что функция, которая по-прежнему считает один-единственный паттерн, работает очень недолго. За 403-405 минут считаются по 403200 паттернов в каждом из 9 потоков. То есть по 0.06 секунды на паттерн.

[Yadryara]

wrest, вот здесь вы и цитату не привели, и свои слова назад не взяли.

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

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

Так вот Yadryara тут предлагает плюнуть на это дело и выкинуть n даже если оно в итоге $pqrs$.

А цитату можно, где я это предлагал?

[wrest]

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

вот здесь вы и цитату не привели, и свои слова назад не взяли.

Цитаты не будет, слова беру назад.

[Yadryara]

Сейчас функция проверки конкретного паттерна у меня выглядит вот так:

fun ( starti:small, kolpop:small, v:vecsmall, maxpredp:small, nu:vecsmall, ip:small, predp:vecsmall, kolpredp:small, bo:vecsmall, T:vecsmall) = {

my(lenv=#v):small;
my(ma=m*v[ip+1]):int; my(n0a=n0*v[ip+1]):int;
my(ostma:vecsmall  = vectorsmall(kolpredp, nompr, ma  % predp[nompr] ));
my(ostn0a:vecsmall = vectorsmall(kolpredp, nompr, n0a % predp[nompr] ));
my(n):int; my(mes):small;
my(kolfac:vecsmall=vectorsmall(lenv,mes,1)); 
my(pro:vec=vector(lenv,mes,1));
my(k48=0):small;
my(kanp):int;

for(i:small = starti, starti + koli - 1, 

for(j = 1, #prter, if( bo[j] == i % prter[j], next(2)));
for(j = 1, #T,     if(  T[j] == i % dopp[j] , next(2)));

kanp = n0 + m * i;
if(!ispseudoprime(kanp,1), next);
n = v[ip+1] * kanp - ip;

kolfac=vectorsmall(lenv,mes,1); pro=vector(lenv,mes,1);

for(nompr=1, kolpredp,
mes = lenv - (ostn0a[nompr] + ostma[nompr]*i - ip + lenv - 1) % predp[nompr];
if(mes<1, next); kolfac[mes]++; pro[mes] *= predp[nompr]; 

if( kolfac[mes] == nu[mes], 
if(!ispseudoprime((n+mes-1)/(v[mes]*pro[mes]),1), next(2))));

for(mes=1,lenv,
if(kolfac[mes]<nu[mes],
if( ispseudoprime((n+mes-1)/(v[mes]*pro[mes]),1), next(2))));

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)));

for(kan = n, n + 15, if(kan % 32 == 0, sta = kan - 15));
print1(n,"     ");
for(kan = sta, sta + 30,
if(numdiv(kan) == kdel, k48 ++ ; print1("1"), print1(" ") ));
print("    ",k48);                            \\ ,"   ",strtime(getwalltime()-t0));

write(log_name2, n,"     ", k48 ); k48 = 0;   \\ ,"     ", n / i + .); 
);return();
}

Потому что в паттерне имеется ровно одно простое. И прога под него заточена.

[Dmitriy40]

Вот этот кусок

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

for(nompr=1, kolpredp,
mes = lenv - (ostn0a[nompr] + ostma[nompr]*i - ip + lenv - 1) % predp[nompr];
if(mes<1, next);

для простых до 2^15 и выполняется с AVX2 порядка 600 тактов, на весь цикл. При условии срабатывания if для всех простых, т.е. без дальнейшей проверки.
Учитывая что ispseudoprime вызывается не более одного раза для каждого места, то общее время для чисел до 6e57 (192 бита) составит не более 600+20000*22<450000 тактов (если ни один вызов ispseudoprime не сработает и не оборвёт цикл проверки по простым).
На PARI этот кусок у меня выполняется около 0.6мс или 2.1млн тактов. С проверкой на превышение kolfac[]>nu[] (но без ispseudoprime) на PARI работает вдвое быстрее.
Как-то не сильно большое ускорение пока что. Хотя резерв ещё есть.

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

if( ispseudoprime((n+mes-1)/(v[mes]*pro[mes]),1), next(2))));

Здесь есть вероятность пропуска решения (ошибки ispseudoprime, может вернуть true на составном числе), очень маленькая, сильно меньше $10^{-13}$, но есть.

[Yadryara]

То есть несмотря на то что к коду нет коментов, Вам всё понятно?

Собственно, я и здесь пытался давать переменным говорящие имена. У Вас было d, я не понимал почему d, а вот mes мне понятно, это же номер места.

Уникальные простые делители, уже довольно давно называю факторами, стало быть koldel (kdel) — это обычное количество делителей, kolfac — количество факторов. Ну конечно до идеала далеко. Ведь, например, омега или nu тоже о факторах говорят. Len — длина, ost — остаток...

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

Учитывая что ispseudoprime вызывается не более одного раза для каждого места, то общее время для чисел до 6e57 (192 бита) составит не более 600+20000*22<450000 тактов (если ни один вызов ispseudoprime не сработает и не оборвёт цикл проверки по простым).
На PARI этот кусок у меня выполняется около 0.6мс или 2.1млн тактов.

Если правильно понимаю, мне нужно было посмотреть пока вот на это: 2.1млн тактов явно больше чем 450000 тактов.

[Yadryara]

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

На PARI этот кусок у меня выполняется

Да, забыл напомнить. Я же не считаю на обычном PARI — компилю и запускаю через Убунту. То есть вот комп ночью освободится, могу позапускать какие-нибудь тесты.

А вот Демис как раз считает на обычном PARI. Но вот есть ли у него на том компе AVX2, совершенно не в курсах.

[Dmitriy40]

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

То есть несмотря на то что к коду нет коментов, Вам всё понятно?

Если присмотреться (чего я не делал из-за неудобного оформления кода) - то да, чего там сложного то.
Только не из-за имён переменных, а я же просто знаю и что и примерно как делает программа, так что длинные имена переменных скорее мешают чем помогают. Лично мне.
И "d" у меня от слова displacement=смещение (в том числе в смысле индекса).

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

Если правильно понимаю, мне нужно было посмотреть пока вот на это: 2.1млн тактов явно больше чем 450000 тактов.

Пока в этом мало смысла: на PARI 99% времени занимает деление с остатком (или сложение векторов по модулю), а на асме наоборот, получение всех 3500 остатков по простым до 2^15 занимает всего 600 тактов, а всё остальное время уйдёт на ispseudoprime (которая ещё не написана!). Зато PARI с ispseudoprime хорошо фильтрует (523:1), а асм без ispseudoprime фильтрует лишь 7.23:1 - это слишком мало, надо или на порядки увеличивать количество простых (с пропорциональным замедлением вычисления остатков) или таки дописывать ispseudoprime (что трудно).

[Dmitriy40]

Написал на асме, без ispseudoprime (только kolfac[]>nu[]), фильтрация 7.22:1 совпадает с PARI (разумеется), скорость 2200 тактов на кандидата (после фильтрации по простым 2-53) для простых до 2^15. В 600 тактов оценки сильно не уложилось почему-то. Без проверок по простым 59-2^15 вообще, только фильтрация по простым 2-53, занимает 1800 тактов.
Без ispseudoprime практического смысла не вижу.

-- 17.01.2026, 03:16 --

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

В 600 тактов оценки сильно не уложилось почему-то.

А, нет, ещё как уложился, просто не так считал, ведь сложение по модулю выполняется в 7.34 больше раз, значит 2200/7.34=300 тактов на однократное вычисление остатков по всем простым до 2^15 даже вместе с проверкой по nu[].

[Yadryara]

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

300 тактов на однократное вычисление остатков по всем простым до 2^15 даже вместе с проверкой по nu[].

Вроде не все нужны, а начиная с 67:

? primepi(2^15)-primepi(65)
%5 = 3494

Мне ничего тестировать пока не нужно?