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

[Yadryara]

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

Не понимаю что за "второй" способ.

Как это можно не понять. Хронологически второй.

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

с 4 foreach+factor или уже без них, только forprime?

Вот это и есть два способа. Один раньше был приведён, второй позже.

Я на память грешу. Счёт закончится, на пустом компе ещё раз проверю.

[wrest]

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

Да. Это ведь не весь рабочий код, в нём могут быть и дополнительные проверки, например factor(x,2^24), которая ещё сколько то отбросит. Или проверка на высшие степени. Или разложение всех чисел цепочки через numdiv и вывод в лог, который потом смотрим глазками или поиском по valids или по числу делителей.

Хорошо, и какие потери допустимы? Просто ведь если вы затем всё равно их проверяете, в чём профит.
Я посмотрел, 95% откидываются на пороге факторизации 2^10

[Dmitriy40]

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

Хорошо, и какие потери допустимы? Просто ведь если вы затем всё равно их проверяете, в чём профит.

В скорости. Есть очень большая разница делать 100000*22 раз numdiv или 20*22 раз. Потому хотелось бы оставить как можно меньше, но приоритет скорости проверки, не отдельного теста, а всех. Коэффициент фильтрации 1млн:1 или 10млн:15 устраивает, оставшиеся можно и досчитать медленным numdiv.

Камрады, у меня в показанном коде опечатка, в строке
if((n+#v-1)%13^3==21-14, next);
должно быть 21-18, а не 21-14. Оказывается строку сдублировал, а поправить забыл. Так фильтрация будет чуть лучше (остаётся 333 vs 357). Но править не буду чтобы цифры остались прежними для сравнения, на оптимизацию факторизации это не влияет.

[wrest]

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

Не понял, это с 4 foreach+factor

Да, этот. Это теперь "эталонный код". Его скорость, при интерпретации в pari/gp, берём за условную единицу.

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

Плохо что мало ускорение от компиляции. Надо разбираться можно ли что-то сделать.

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

-- 03.12.2025, 21:59 --

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

Коэффициент фильтрации 1млн:1

Тогда ваш "эталонный код" не удовлетворяет, т.к. у него (на даваемом вами примере) 1млн:185

[Dmitriy40]

wrest
Да я думал речь про forprime, там встроенных функций мало (деление и редкая ispseudoprime(x,1) aka Mod(2,x)^(x-1)), вот для него от компиляции ускорение должно быть побольше.

-- 03.12.2025, 22:15 --

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

Тогда ваш "эталонный код" не удовлетворяет, т.к. у него (на даваемом вами примере) 1млн:185

Да. Если получится за примерно то же время фильтровать лучше - отлично.
В варианте с forprime - получается, добавлением двух строк, одну внутрь цикла, одну после (которая и улучшает фильтрацию 185:1).

[Yadryara]

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

Учитывая что все числа совпадают с моими, ищите опечатку в редакции 2^20.

Какая там может быть опечатка — непонятно. 21-я и 22-я степени работают нормально.

В общем интересное кино. В интервале 2^20-1 — 2^20+0.9 довольно быстро заканчивает не показывая даже время.

А вот при 2^20-1.1 и 2^20+1 уже работает нормально.

[Dmitriy40]

Покажу красивую замену той кучке if что у меня выше в коде сразу после вычисления n и которая эквивалентна длинному if в программах VAL:
if((n+#v-1)%3^6<#v, next);\\3^5 уже есть в паттерне
forprime(p=5,19, if((n+#v-1)%p^3<#v, next(2)); );\\А эти простые есть лишь в квадратах
По скорости отличия в рамках погрешности, медленнее где-то на 0.1с из 4.9с.
Красота в частности в том что можно 19 заменить на 53 и будет замена и второму if у VAL, который уже несколько мест запрещал (исходно три, сколько простых ищем на местах лишь с p). Правда так медленнее уже на 0.5с из 5.0с.
После компиляции разница может стать чуть больше так как тут длинное деление, а раньше было деление i%p, что укладывается даже в int32, не говоря уж про int64.

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

Какая там может быть опечатка — непонятно. 21-я и 22-я степени работают нормально.

Хм, это может быть неоднократно вылеченный глюк в forprime:

Changelog писал(а):

Done for version 2.17.1 (released 24/12/2024):
Fixed
...
11- forprime(p=524288,1048576,1) -> crash [#2584]
forprime(p=1048607,1048617,1) -> oo loop [F11]

Какие-то у них вечные проблемы около 2^20 ... Из-за попытки оптимизации forprime.
Хотя у меня на версии 2.17.3 работает нормально.
Проверьте в винде на вашей версии. Или в WSL если глюк в винде.

[wrest]

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

Да я думал речь про forprime, там встроенных функций мало (деление и редкая ispseudoprime(x,1) aka Mod(2,x)^(x-1)), вот для него от компиляции ускорение должно быть побольше.

Я пока не вник, дайте весь код пож-ста целиком (аналогичный эталону, то есть с той же генерацией n и заменой проверяющей части), я скомпилирую и запущу.

Пока я придумал, что в варианте c factor(n,D) было бы неплохо проверять сперва те члены кортежа, у кого меньше nu[i] и соответственно больше вероятность переполниться множителями, это даст выигрыш в ~1,25 раз

Одновременная факторизация по всему кортежу что-то не даётся мне пока.

-- 04.12.2025, 03:07 --

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

Проверьте в винде на вашей версии. Или в WSL если глюк в винде.

У Yadryara в WSL теперь есть "штатно" 2.17.2 и "опционально" 2.18.1

[Dmitriy40]

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

Я пока не вник, дайте весь код пож-ста целиком (аналогичный эталону, то есть с той же генерацией n и заменой проверяющей части), я скомпилирую и запущу.

Возьмите код эталона, вот эти строки

\\Здесь начинается проверка конкретного n
   foreach([1..#v],d, g=factor((n+d-1)/v[d],2^12); nf=matsize(g)[1]; if(nf>nu[d], next(2)); if(nf==nu[d] && !ispseudoprime(g[nf,1],1), next(2)); );
   foreach([1..#v],d, g=factor((n+d-1)/v[d],2^14); nf=matsize(g)[1]; if(nf>nu[d], next(2)); if(nf==nu[d] && !ispseudoprime(g[nf,1],1), next(2)); );
   foreach([1..#v],d, g=factor((n+d-1)/v[d],2^17); nf=matsize(g)[1]; if(nf>nu[d], next(2)); if(nf==nu[d] && !ispseudoprime(g[nf,1],1), next(2)); );
   foreach([1..#v],d, g=factor((n+d-1)/v[d],2^20); nf=matsize(g)[1]; if(nf>nu[d], next(2)); if(nf==nu[d] && !ispseudoprime(g[nf,1],1), next(2)); );
\\Проверка закончена, что осталось то осталось, подсчитаем сколько их и выведем в консоль для проверки

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

\\Здесь начинается проверка конкретного n
   nf=vector(#v,d,1); nn=vector(#v,d,1);\\Вектор количества делителей (omega) и вектор накопления их для каждой позиции
   x=n+#v-1;\\Чуточку ускоряет
   forprime(p=59,2^20,\\Проверяем делимость только на такие простые
      d=#v-x%p; if(d<1, next); nf[d]++; nn[d]*=p;\\Получение остатка, проверка что он (и простое p) попадает в кортеж, накопление числа и самих делителей
      if(nf[d]>nu[d], next(2));\\Если уже перебор, то отбрасываем
      if(x%p^2<#v, next(2));\\Проверка на степени выше первой, такие n сразу отбрасываем
      if(nf[d]==nu[d] && !ispseudoprime((n+d-1)/v[d]/nn[d],1), next(2));\\Если ровно сколько нужно проверим закончена ли факторизация и если нет - тоже отбрасываем
   );
   foreach([1..#v],d, if(nf[d]<nu[d] && ispseudoprime((n+d-1)/v[d]/nn[d]), next(2)); );\\Проверка что разложение закончено, а делителей меньше требуемого
\\Проверка закончена, что осталось то осталось, подсчитаем сколько их и выведем в консоль для проверки

Последнего цикла проверок в эталоне с factor нет, можете и тут его закомментировать, именно он кардинально снижает количество цепочек с 22 (185) до 1.
Но результат эталону не равен в точности:

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

100000/22, time: 5,085 ms
Осталось 22 вместо 20, это не ошибка, в двух из них попалось лишнее простое меньше 59 (точнее оно оказалось в неправильной степени чем есть в v[]), factor это обнаружил и кортеж отбросили, эта проверка этого не обнаружила и посчитала в 22.

[Yadryara]

Ну да, я уже и так вспомнил, что Дмитрий ранее писал про глюк в форпрайм.

Я по привычке работаю пока в Винде. Это у меня PARI 2.17.0

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

Пока я придумал, что в варианте c factor(n,D) было бы неплохо проверять сперва те члены кортежа, у кого меньше nu[i]

Это придумано уже лет сто назад, но никто не мешает переоткрывать. Может какие-то новые ходы придумаются. Главное, что вы наконец-то начали лучше понимать задачу.

[Dmitriy40]

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

Пока я придумал, что в варианте c factor(n,D) было бы неплохо проверять сперва те члены кортежа, у кого меньше nu[i] и соответственно больше вероятность переполниться множителями, это даст выигрыш в ~1,25 раз

Это и предлагал Yadryara когда поделил 21 число на 1+3+17, правда у него порядок получился pq+pqrs+pqr.
Да, с factor разделение одного первого цикла с порогом 2^12 на два, pq+остальные, ускоряет в 1.23 раза. Разделение и второго цикла с порогом 2^14 эффекта уже не даёт, ускорение менее 0.1с из 4с.
А в моём предложении с одним forprime факторизации членов кортежа уже нет, потому это смысла не имеет.

[wrest]

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

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

компиляция ускоряет в 3 раза.

[Dmitriy40]

wrest
Хотелось бы сравнения с эталоном, который с factor. Оба с компиляцией.

[wrest]

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

Хотелось бы сравнения с эталоном, который с factor. Оба с компиляцией.

эталон интерпретация 39
эталон компиляция 28
forprime интерпретация 39
forprime компиляция 13

Да, ну и подготовка же ещё (одна и та же). Интерпретация 3, компиляция 2.
Это до миллиона.

[Yadryara]

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

Я по привычке работаю пока в Винде. Это у меня PARI 2.17.0

Для этого варианта для forprime всё плохо:

1-й способ        1000000/189   28,941 ms
2-й (forprime)    1000000/200   46,242 ms

Теперь попробую с компиляцией. Как понимаю, мне не нужно идти в PARI 2.15, а нужно идти в 2.18.2 и там пытаться скомпилить.

-- 04.12.2025, 04:37 --

Или надо идти в старый каталог, потому что там gp2c есть?