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

[Yadryara]

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

Что значит "проверит дальше"? Что должна получить функция на вход и что должна выдать на выходе?

На вход частное от того самого числа, которое успешно прошло предыдущие проверки по (factor, 2^... )

И на выходе ровно то же, то есть либо 0 либо nu.

[wrest]

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

На вход частное от того самого числа, которое успешно прошло предыдущие проверки по (factor, 2^... )

И на выходе ровно то же, то есть либо 0 либо nu.

Да, просто вызываете omega(rn,rm,0) где rn - то что надо факторизовать ("частное"), rm - лимит по множителям в этом "частном" (допустим всего в подходящем числе вам надо чтобы было 4 множителя, а на первом этапе вы уже нашли 1, значит найти надо ещё rm=3 или вернуть ноль если найдётся больше). Но omega_upto() всё равно начнёт с trial division. Чтобы она не проходила по всей таблице простых, перед вызовом omega_upto() надо установить например default(factorlimit,100) и потом не забыть вернуть обратно на default(factorlimit, 2^20) чтобы не было побочных эффектов при использовании встроенных факторизаций pari/gp. Тут может потенциально быть проблема, если найдутся множители между 2^14 и 2^20, но надо проверять. Я не эксперементировал с поведением omega_upto() при пониженном factorlimit

[Yadryara]

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

rm - лимит по множителям

Ну так у меня он maxnu.

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

Чтобы она не проходила по всей таблице простых, перед вызовом omega_upto() надо установить например default(factorlimit,100) и потом не забыть вернуть обратно на default(factorlimit, 2^20)

Чего-то не догоняю. Нужно запомнить 2 миллиона предвычисленных простых, скажем от $2^{20}$ до $2^{25}$ и проверять только по ним.

[wrest]

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

Чего-то не догоняю. Нужно запомнить 2 миллиона предвычисленных простых, скажем от $2^{20}$ до $2^{25}$ и проверять только по ним.

Если только по ним, то omega_upto() не подходит. Ну и переборные методы тут уже будут замедляться.
Используйте factorint(rn, 1+8) это не гарантирует нахождение больших множителей, но вам и не надо.

-- 02.12.2025, 13:22 --

Yadryara
Dmitriy40

Вообще я рекомендовал бы вам почитать радел
7.4 Higher arithmetic over Z: primes, factorization.
в гайде
Users Guide to the PARI library (version 2.17.0) лежит тут https://pari.math.u-bordeaux.fr/pub/par ... ibpari.pdf
Описанные там функции можно "установить" в pari командой install (без компиляции чего либо, эти функции уже есть в библиотеке и объявлены в ней) возможно вы там найдёте что-то интересное

[Yadryara]

Да, надо переносить проверку вовнутрь:

Кол-во случаев когда частное делится на 67 составляет 31.9% от всех цепочек-кандидатов
Кол-во случаев когда частное делится на 71 составляет 29.9% от всех цепочек-кандидатов
Кол-во случаев когда частное делится на 73 составляет 29.3% от всех цепочек-кандидатов

Ну и так далее, видимо.

[wrest]

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

Кол-во случаев когда частное делится на 67 составляет 31.9% от всех цепочек-кандидатов

Сообщаю, что я ничего не понял тут. Считаю, что это только для посвященных

[Yadryara]

wrest, ну вы же говорили что Дмитрия понимаете Это я его предложение проверил. Буду ещё проверять.

[Dmitriy40]

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

Очевидно: чтобы wresta не грузить этими вычислениями.

По моему одна строка простых вычислений проще длинных таблиц и подготовки файла.

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

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

А как определили, что не хочу сделать понятным для других ?

Отсутствие форматирования, отсутствие комментариев.

+1.

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

Ну вот код, где и nu[] и maxnu и omega_upto используются:

И тоже без нормального оформления - потому не вызывает желания вникать.

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

А на Си вы будете искать начало "руками", то есть начнёте цикл по i с единицы и будете сравнивать i-й элемент таблицы простых со start и когда превысит, при условии что ещё не конец диапазона end, выполнять тело цикла. Чтобы избежать этого ручного поиска, вам надо будет предварител но вычислить положение нужного вам простого и задавать начало и конец диапазона в терминах $\pi (start)$ сразу пропуская поиск nextprime()

Не вижу причин избегать этого ручного поиска - он по любому на порядки быстрее nextprime() и ispseudoprime(), ведь речь идёт о малых простых, гарантированно имеющихся в предпосчитанной таблице, т.е. вся проверка сводится просто к сравнению двух малых чисел и всё, это весьма быстро.
И положение вычислять не нужно.
И nextprime() не нужна, список малых простых готов.
Т.е. на C код будет примерно таким (упрощаю):

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

int isnumdiv(GEN n, int start=67, int end=2^14) {
  for(int j=0; j<1900 && pi[j]<end; j++) {
    if(p[j]<start) continue;//Вот и пропуск простых до start
    if(n%p[j]>0) continue;
    ...
  }
}

Как прекрасно видно весь пропуск ненужных 19-ти простых в разы быстрее одной команды длинного деления.

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

Вообще я рекомендовал бы вам почитать радел
7.4 Higher arithmetic over Z: primes, factorization.

Посмотрел, ничего особо нужного не нашёл.

Yadryara
Я тоже не понял про какой именно вариант проверок речь. Какая длина паттерна, какое именно частное (любое? первое?) ...
Чтобы понять пришлось самому подумать "что бы это могло быть". И только тогда стало очевидно что пытались проверить формулу $1-(1-\frac{1}{p})^{21}$, хотя в её правильности сомнений как бы и нет.

[wrest]

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

Не вижу причин избегать этого ручного поиска - он по любому на порядки быстрее nextprime() и ispseudoprime()

Конечно, я ж и написал что надо руками. Просто если вдруг захочется избежать и этого, то можно попадать сразу (вывозов факторизации будет много, но во всех будет один и тот же диапазон по $\pi(n)$ который можно просчитать заранее. Слёзы конечно.

[Dmitriy40]

Камрады, очередное ускорение, теперь в 20+ раз!
Рассмотрим приведённый ранее код, реализующий часть функционала factor(n+d,2^14):
foreach(z16,d, nf=0; x=n+d; forprime(p=67,2^14, if(x%p==0, nf++; x=x\p); ); if(nf>4, next(2) , nf==4 && !ispseudoprime(x), next(2) , nf<4 && ispseudoprime(x), next(2)); )
На уровне идеи тут каждое из чисел n+d, приму что d=[0..21], проверяется не делится ли оно на простые 67...2^14.
Отдельно замечу что вычислять x=(n+d)/v[d+1] до использования в ispseudoprime (куда выполнение может и не дойти) нет необходимости, это тоже экономит часть длинных делений.
Но эту проверку можно сделать и по другому:
forprime(p=67,2^14, d=(n+21)%p; if(d>=21, next); ... )
Т.е. просто посчитать остаток от деления последнего числа на простое и если он меньше 21, то одно из чисел, а именно 21-d, разделилось на p. Далее можно уже его проверять как хочется.
Больше одного числа разделиться не может, так как min(p)>21.
В итоге не надо делать 22 деления на каждое простое, достаточно одного.
Да, код проверки будет сложнее, nf заменится на nf[] длиной 22, вместо z16[] нужен nu[] (требуемое количество делителей, которое omega), но думаю оно стоит.

-- 02.12.2025, 16:59 --

Понятно что 20 раз от factor(n,2^14) не получится, но какое-то должно быть, и не совсем малое.
А уж если скомпилить, да ещё и поправить переменные в цикле, там ведь лишь одна длинная, n+21, то будет ещё побыстрее.

[wrest]

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

Камрады, очередное ускорение, теперь в 20+ раз!

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

[Yadryara]

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

И только тогда стало очевидно что пытались проверить формулу $1-(1-\frac{1}{p})^{21}$, хотя в её правильности сомнений как бы и нет.

Чё-то больно сложно. Попросту ширина полосы примерно определяет вероятность попадания в неё $\frac{22}{67}$, $\frac{22}{71}$, $\frac{22}{73}$ ...

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

[Dmitriy40]

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

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

Для n%p это неважно, частное (которые легко сохранить в массив) понадобится лишь для ispseudoprime, до которой может и не дойти.

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

Понятно что 20 раз от factor(n,2^14) не получится, но какое-то должно быть, и не совсем малое.

На M48n21p0 (без искомых простых) времена выполнения:

                порог:  2^12    2^14    2^17    2^20
foreach+forprime:       7.7с    19.1с   96с     576с
foreach+forprime:       7.7с    8.2с    9.1с    10.8с   - последовательные тесты без простых до предыдущего порога
forprime:               3.1с    3.6с    4.0с    5.2с    - новый
foreach+factor:         1.8c    2.1с    5.9с    34с
foreach+factor:         1.8с    1.8с    1.9с    2.0с    - последовательные тесты

Где последовательные это значит что с большим порогом запускается только если все предыдущие не сработали (не отбросили кандидата).
Ускорение есть, но не так уж сильное.
И factor перегнать не удалось. Надо смотреть что будет после компиляции.


В примерах кодов выше у меня ошибки. Но идея везде правильная.

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

Чё-то больно сложно. Попросту ширина полосы примерно определяет вероятность попадания в неё $\frac{22}{67}$, $\frac{22}{71}$, $\frac{22}{73}$ ...

Тем более.

[Yadryara]

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

И factor перегнать не удалось.

Ну может надо комбинировать. Установить делимость на 67 — (250-500), а дальше фактором допроверять именно числа которые разделились. В общем как всегда сложно и интересно.

[Yadryara]

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

В примерах кодов выше у меня ошибки.

Исправил я Ваши ошибки. Вроде бы все.

Плюс реализовал идею с порогом в 512. То есть сейчас считает вроде правильно и быстро. Но не сильно быстро — в полтора раза при 3-х потоках против обычных 12-ти. Сейчас уменьшил до 256 и запустил уже все 12 потоков.

Но нет, вроде нет ускорения.