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

[Yadryara]

wrest

А на чём у вас эта omega_upto написана?

Я вижу комент: "Этап 1: обработка малых простых (2, 3, 5, 7)"

Но ведь поступающие на вход числа гарантированно не будут делиться не то что на 7, а вплоть до 61 включительно. Ведь можно сэкономить кучу времени, не делая эти проверки?

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

Так что, если есть интерес, просьба написать несколько вариантов этой функции и по-разному назвать.

Ещё важнейший момент. Сейчас первая проверка делается по factor(n, 2^14). И Вашу омегу тоже желательно огранить сверху примерно таким же порогом.

Думаю, что я смогу менять всякие параметры в исходном коде и раз за разом пересобирать.

[wrest]

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

А на чём у вас эта omega_upto написана?

На Си. Но во "фреймворке" pari/gp (с тамошней типизацией, использованием внутренних функций управляющих факторизацией и т.п.).

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

Но ведь поступающие на вход числа гарантированно не будут делиться не то что на 7, а вплоть до 61 включительно. Ведь можно сэкономить кучу времени, не делая эти проверки?

Это универсальная функция. Можете делать проверку на отсуствие малых простых множителей самостоятельно

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

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

Проверка на бесквадратность управляется третьим параметром. 1- оставлять бесквадратные, 0 - отбрасывать.

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

Так что, если есть интерес, просьба написать несколько вариантов этой функции и по-разному назвать.

Сперва потестируйте эту.

-- 01.12.2025, 10:35 --

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

Ещё важнейший момент. Сейчас первая проверка делается по factor(n, 2^14). И Вашу омегу тоже желательно огранить сверху примерно таким же порогом.

Надо делать так, чтобы потом не надо было переписывать. Чётко сформулируйте требования - что должна возвращать функция при каких входных параметрах. То что вы пишете - понятно вам, но часто непонятно например мне. До 2^14 всего 1900 простых чисел, проверку множителей только до этого порога можно написать как самостоятельную быструю функцию, лезть в ядро не надо. Ядро полезно тем, что там есть сложные методы факторизации MPQS, ECM и т.п.
Там довольно сложная факторизационная машинерия (встроенная в pari), можете попробовать вникнуть. Почти всё управление в ifactor1.c

[Yadryara]

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

Сперва потестируйте эту.

Так уже. Она проигрывает фактору с 2^14 не просто в разы, а во много раз. В десятки или в сотни раз уже не очень интересно.

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

Это универсальная функция. Можете делать проверку на отсуствие малых простых множителей самостоятельно

Не понял. Как именно? Я в Сях не копенгаген.

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

Проверка на бесквадратность управляется третьим параметром. 1- оставлять бесквадратные, 0 - отбрасывать.

Отлично.

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

Надо делать так, чтобы потом не надо было переписывать.

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

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

То что вы пишете - понятно вам, но часто непонятно например мне.

Это ничего, впс в отличие от довольно многих форумчан, на вопросы отвечает.

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

До 2^14 всего 1900 простых чисел, проверку множителей только до этого порога можно написать как самостоятельную быструю функцию, лезть в ядро не надо.

Вам виднее, но это обязательно надо сделать, ибо пока проигрыш по скорости колоссальный.

[wrest]

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

Думаю, что я смогу менять всякие параметры в исходном коде и раз за разом пересобирать.

Ну не знаю... Надо же как-то измерять эффект, я бы предложил вам сосредоточиться на этом.
Раз за разом пересобирать "на авось" это странный метод...

[Yadryara]

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

Надо же как-то измерять эффект,

Будьте покойны, измеряю. Сам уже целый день не считаю, в основном только и делаю, что измеряю. Пока на этих 42 числах. Самое важное пока, это порог в районе $2^{14-15}$

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

Это универсальная функция.

Скорость важнее универсальности.

[wrest]

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

Вам виднее, но это обязательно надо сделать, ибо пока проигрыш по скорости колоссальный.

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

Так уже. Она проигрывает фактору с 2^14 не просто в разы, а во много раз. В десятки или в сотни раз уже не очень интересно.

Я не понимаю, что за соревнования. Код давайте.
Ощущение такое, что я вам заменил карьерный самосвал БелАЗ на Камаз, а вы мне говорите, что Камаз таки проигрывает мотоциклу в перевозке грузов, если масса груза меньше 2^14...2^15 грамм.

-- 01.12.2025, 11:37 --

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

Пока на этих 42 числах. Самое важное пока, это порог в районе $2^{14-15}$

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

Скорость важнее универсальности.

Мне нужен переводчик с вашего языка. Dmitriy40 вы понимаете, о чём пишет Yadryara?

[Yadryara]

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

Я не понимаю, что за соревнования. Код давайте.

Ну вот, посмотрите пока как ведёт себя фактор. Меняйте параметр st1. Я обнаружил резкие скачки после 20-й степени. Причём и на 42-х и на 1911 числах.

install(omega_upto,GGG);

{t0=getwalltime();print;

nukdel = [4,16,16,16,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8];  

nu     = [2, 4, 4, 4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3];  

st1 = 14;
maxnu = 4;

print(st1);print;

name = fileopen("Chisla_1.txt");

while( n = eval(filereadstr(name)),

nom++;

t1=getwalltime();

fac = factor(n,   2^st1   ); kunp = matsize(fac)[1];

\\fac = factor(n); kunp=matsize(fac)[1];


if(kunp                       == nu[(nom-1)%21 + 1],

if(ispseudoprime(fac[kunp,1]),

kpod++;
print1(kpod, ".   ", nom, "     kunp = ", kunp, "   ");
\\print(strtime(getwalltime()-t1));
print
)

,
kunp > nu[(nom-1)%21 + 1] || ispseudoprime(fac[kunp,1])

,
 next ); 


);

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

[Dmitriy40]

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

Мне нужен переводчик с вашего языка. Dmitriy40 вы понимаете, о чём пишет Yadryara?

Да, я же сам и писал аналогичную программу и все эти методы ускорения использовал.
Только я не согласен с его желанием сделать всё сильно специфично, я за универсальность - если она не сильно тормозит.

И да, проще сделать перебор делителей до указанного порога руками. От PARI придётся задействовать лишь деление с остатком и ispseudoprime() чтобы понимать закончилась факторизация или нужно продолжать (вероятность что наберётся делителей больше требуемого мала). А для ускорения - цикл по входному вектору чисел сделать внутри цикла перебора простых делителей.

-- 01.12.2025, 12:50 --

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

До 2^14 всего 1900 простых чисел, проверку множителей только до этого порога можно написать как самостоятельную быструю функцию, лезть в ядро не надо.

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

[wrest]

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

Ну вот, посмотрите пока как ведёт себя фактор.

factor(n,D) ведёт себя так, что производится только пробное деление на простые не превышающие D
В документации написано что не стоит делать D>10^9

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

Я обнаружил резкие скачки после 20-й степени.

Потому что у вас primelimit = 1048576 что как раз и есть 2^20 - таиблица простых закончилась и надо её пополнять, каждую факторизацию
Увеличьте primelimit (ценой разрастания таблицы простых) и скачков не будет.
Но всё-таки почитайте что пишут в мануале про параметр D в функции factor:

Цитата:

This routine uses trial division and perfect power tests, and should not be used for huge values of D (at most 10^9, say): factorint(, 1 + 8) will in general be faster. The latter does not guarantee that all small prime factors are found, but it also finds larger factors and in a more efficient way.

Вы, мне кажется, сравниваете тёплое с мягким. Ещё раз: сформулируйте чего вы хотите и чем готовы пожертвовать.
omega_upto() не конкурент factor(n,2^14), вообще.

-- 01.12.2025, 14:43 --

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

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

Факторизационный движок pari проверяет остатки на простоту при помощи ispseudoprime как раз, если только не установлен флаг factor_proven (ну или смотрит в таблицу)

-- 01.12.2025, 14:49 --

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

И да, проще сделать перебор делителей до указанного порога руками.

Уже есть. В коде вот тут post1711225.html#p1711225 если сделать выход перед комментарием
/* --- Этап 3: ifac_start только для составного остатка --- */то останется как раз только пробное деление до factorlimit, с ранним выходом по перебору простых множителей.

[Yadryara]

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

Вы, мне кажется, сравниваете тёплое с мягким.

Конечно. И в сложных задачах это не редкость.

Я вам аналогию приведу. Круче чем с Камазом и мотоциклом.

Вот у меня есть задача: построить гараж на всю жизнь. А сколько я проживу? Не знаю.

Значит надо с запасом строить? Ну, допустим. А с запасом это на сколько, на сто лет или на тысячу? Опять непонятно. А из чего строить? Самому блоки класть или профессионалов нанимать? С кровлей что делать? Стропила подпирать или и так не сильно провиснут? А окна вставлять туда? Если да, то в каких местах? Делать их открывающимися? Гвоздями обрешётку крепить или саморезами? Сороковкой или пятидесяткой?

И таких вопросов миллиард.

Ну вот и строишь интуитивно. Потому что построить вроде лучше чем как буриданов осёл, годами выбирать материалы и думать над вопросами, на которые не существует точных ответов.

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

Ещё раз: сформулируйте чего вы хотите и чем готовы пожертвовать.

В настоящее время ищем цепочку с 48-ю делителями. Пока что длиной 22. И я хочу её за месяц найти. Это достаточно конкретно? Боюсь что нет.

Чем готов пожертвовать? Свободным временем, например. На интересные задачи его обычно не жалко.

Можно пользоваться универсальной прогой, тыщу лет искать и не найти. Зато универсальная.

А можно заточить программу под конкретную задачу и за месяц найти. И в этом смысле скорость важнее универсальности.

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

omega_upto() не конкурент factor(n,2^14), вообще.

А вы понимаете, что это многозначная фраза? И её можно понимать в разных смыслах? Карета ракете тоже не конкурент. Они весьма разные.

Код, который я привёл выше, используется для счёта в настоящее время, хотя не именно в таком виде. Его надо ускорять.

[wrest]

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

Код, который я привёл выше, используется для счёта в настоящее время, хотя не именно в таком виде. Его надо ускорять.

Ok, ну как сможете сфокусироваться и ясно сформулировать что же тормозит и что ускорять, сообщайте "Мне надо ускорить вот этот код, ну вернее не этот а похожий на него" -- лично я тут пас, сорри.
Считайте, что factor(n,2^k) для k<20 -- это максимально ускорено уже. omega_upto() тут вам не поможет, т.к. она написана так, чтобы гарантировать, что независимо от числа, определяется "подходит" оно или нет.
Но trial division с ранним выходом есть и в коде omega_upto, как я писал ранее. Всё что до 3-го этапа -- это оно и есть. Код простой. Можете его модифицировать и делать выход сразу после trial division, или добавить верхний порог если считаете, что например на 2,3,5,7 делить не надо и пытаться.

Если вы не собираетесь повышать порог отбрасываемых остатков, то trial division подойдёт. Если собираетесь, то не подойдёт.

[Yadryara]

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

Увеличьте primelimit (ценой разрастания таблицы простых) и скачков не будет.

Увеличил — время для 2^21 то же самое.

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

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

Код, который я привёл выше, используется для счёта в настоящее время, хотя не именно в таком виде. Его надо ускорять.

Ok, ну как сможете сфокусироваться и ясно сформулировать что же тормозит и что ускорять, сообщайте

Сообщаю: если буду знать как ускорить приведённый код, скорее всего буду знать как ускорить рабочий.

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

omega_upto() тут вам не поможет, т.к. она написана так, чтобы гарантировать, что независимо от числа, определяется "подходит" оно или нет.

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

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

Но trial division с ранним выходом есть и в коде omega_upto, как я писал ранее. Всё что до 3-го этапа -- это оно и есть. Код простой.
Можете его модифицировать

Попробую потихоньку. Пока не понимаю что такое trial division.

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

добавить верхний порог если считаете, что например на 2,3,5,7 делить не надо и пытаться.

Не надо даже пытаться делить на 2,3,5,7, ... , 61. Не разделится.

Думаю, что так же считают все, кто понимает как строятся паттерны.

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

Если вы не собираетесь повышать порог отбрасываемых остатков, то trial division подойдёт. Если собираетесь, то не подойдёт.

Не понимаю что такое порог отбрасываемых остатков.

-- 01.12.2025, 19:50 --

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

Пока не понимаю что такое trial division.

Ну понял, лучше даже говорить не триал, а тривиал.

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

Не понимаю что такое порог отбрасываемых остатков.

Появилось ощущение, что здесь очередная терминологическая путаница. Потому что кое-кто частное называет остатком.

[wrest]

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

Попробую потихоньку. Пока не понимаю что такое trial division.

Метод факторизации перебором делителей.
https://en.wikipedia.org/wiki/Trial_division

https://ru.wikipedia.org/wiki/%D0%9F%D0 ... 0%B5%D0%B9

-- 01.12.2025, 20:44 --

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

Потому что кое-кто частное называет остатком

Согласен, неаккуратно выразился.

[Dmitriy40]

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

Ok, ну как сможете сфокусироваться и ясно сформулировать что же тормозит и что ускорять, сообщайте

Смотрите, чтобы отбросить кандидата надо проверить (немного упрощаю):
foreach(z16,d, if(numdiv(n+d)<>16, next(2)); )
Т.е. если количество делителей неправильное, то отбросить кандидата и перейти к следующему.
Это медленно. И тормозит разумеется numdiv().
Но известно что довольно часто числа имеют небольшие делители, например меньше 2^14, потому появилась идея заменить numdiv() на такую конструкцию (тоже упрощаю):
foreach(z16,d, fac=factor(n+d,2^14); nf=matsize(fac)[1]; if(nf>4, next(2) , nf==4 && !ispseudoprime(fac[nf,1]), next(2) , ispseudoprime(fac[nf,1]), next(2)); )
Здесь проверяется: что малых (до указанного порога 2^14) делителей уже слишком много чтобы получить ровно 16 делителей; что делителей уже 16 и последнее число составное (значит делителей точно больше 16); что делителей меньше 16 и разложение закончено. Каждое из этих условий позволяет отбросить кандидата не проверяя остальные места.
Да, это фактически попытка делить на простые до 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)); )
на PARI медленнее factor(n,2^14). Не удивительно, для интерпретатора кучка команд всегда медленнее встроенной функции.
Хотя в таком виде его можно наверное ускорить засунув if внутрь цикла forprime (оставив последнее условие с nf<4 && ispseudoprime(x) после цикла).
Вот можете попробовать скомпилировать этот код как функцию isomega4(n,z16,nd=4,porog=2^14,start=67), только next(2) замените на return 0 и добавьте в конце return 1, будет ли он быстрее кода с factor(n,2^14).
Уходить в ECM, MPQS и прочие тут не нужно, это всё слишком долго.

Можно наверное немного ускорить заменив nf==4 && !ispseudoprime(x) на nf==4 && !ispseudoprime(x,1) (что почти эквивалентно nf==4 && lift(Mod(2,x)^(x-1))<>1), так не будет точной проверки на простоту, но она именно тут и не нужна, тут нужна точная проверка на составное, а обе конструкции именно это гарантированно и делают. Какая из них быстрее после компиляции мне неведомо.

А ещё можно ускорить весь froeach переставив foreach и forprime местами и сделав nf и x векторами длиной #z16. Тогда сначала все места будут проверены на делимость на 67, потом на 71, потом на 73 и так далее до 2^14 и если вдруг найдётся место в конце кортежа, позволяющее его отбросить при небольших p, то так будет быстрее, ведь не придётся делить места перед ним на все простые до 2^14. Но если можно отбросить по первым местам с p около 2^14, то так будет медленнее, ведь придётся на все простые до 2^14 поделить не только первые места, а все. И тут вопрос что пересилит, уменьшение доли запрещённых остатков с возрастанием p или вероятность отбросить кандидата по малым p.

PS. Совет, прежде чем мучить ИИ готовым кодом всё же выясните что именно нужно заказчику. Потому что omega_upto() в таком виде ему точно не нужна, ему нужно ускорить показанный выше цикл foreach, и лучше весь, а не отдельно numdiv или factor. Причём ещё хорошо бы посмотреть в С код и проверить что условия выхода проверяются в порядке увеличения времени /сложности, а не абы как, нужна оптимизация скорости для случаев отказа (срабатывание next(2) или return 0), они на порядки чаще.

[wrest]

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

Здесь проверяется: что малых (до указанного порога 2^14) делителей уже слишком много чтобы получить ровно 16 делителей; что делителей уже 16 и последнее число составное (значит делителей точно больше 16); что делителей меньше 16 и разложение закончено. Каждое из этих условий позволяет отбросить кандидата не проверяя остальные места.

omega_upto() вот именно это и делает. Но если в результате trial division до простых меньших factorlimit найдено слишком мало делителей и остаток составной, то пытается разложить нефакторизованный остаток (частное) "тяжелыми" методами. Соответственно, если этот остаток большой (ну скажем 10^40) и при этом полупростой, то работает долго. Если же до factorlimit нашлось слишком много множителей, то выходит и возвращает ноль. Ну вот допустим n порядка 10^50 и вы проверяете не является ли $n=pqrs$, вы уже нашли что pq порядка 10^10, и осталось qs порядка 10^40 причем вы знаете что qs составное т.к. проверили его pseudoprime-ом, и тут возможно, что они оба по 10^20 Так вот Yadryara тут предлагает плюнуть на это дело и выкинуть n даже если оно в итоге $pqrs$. А omega_upto() продолжает и находит q и s. Я-то не в курсе, а надо ли плюнуть. Не ну надо так надо

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

Совет, прежде чем мучить ИИ готовым кодом всё же выясните что именно нужно заказчику.

Я пытался Но так и не понял например позицию по бесквадратности. Например проскакивало, что если попадётся p^2 то надо выкинуть, а p^3 можно и оставить.