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

[Dmitriy40]

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

Но если в результате trial division до простых меньших factorlimit найдено слишком мало делителей и остаток составной, то пытается разложить нефакторизованный остаток (частное) "тяжелыми" методами.

Вот это и лишнее. Лучше проверить остальные места кортежа, вдруг там получится отбросить кортеж без погружения в тяжёлые медленные методы.
Задача: как можно быстрее найти причину отбросить кандидата. Не одно число, а весь кортеж.

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

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

Потому что задаёте неправильные вопросы. Позиция зависит от скорости проверки, если не медленнее - можно и сделать, если тормозит - выкинуть нафиг. Для начала - выкинуть. И ещё зависит от метода поиска делителей, если запустился ECM, то сделать пару лишних делений для проверки степени - слёзы и лучше сделать, а вот если каждое деление эквивалентно проверке лишнего простого делителя (в trial division), то лучше не проверять (степени встречаются порядка 0.1% от всех проверяемых чисел, столь редкое ускорение отбрасывания кандидата незаметно). С другой стороны, только сейчас подумал, даже 0.1% это всё равно больше чем 1/p (вероятность делимости на p) для p>1000, т.е. для p>1000...3000 выгоднее проверить и степени вместо проверки очередного простого.

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

-- 01.12.2025, 22:20 --

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

и осталось qs порядка 10^40 причем вы знаете что qs составное т.к. проверили его pseudoprime-ом, и тут возможно, что они оба по 10^20 Так вот Yadryara тут предлагает плюнуть на это дело и выкинуть n даже если оно в итоге $pqrs$.

Не заметил такого предложения, выкидывать qs если оно может дать pqrs. В коде выкидывание происходит только если pqrs точно не получается (но без проверки на кубы и высшие степени). И кстати проверить qs на куб (возможно составного) и высшие степени гораздо быстрее isprime, но это встречается настолько редко, что проще не делать и игнорировать возможность кубов и выше (отбрасывать такие n).
А вот квадраты можно и проверять, для простых больше пары тысяч (порог подбирается тестами и чтобы не перекомпилить каждый раз передавать его параметром).

-- 01.12.2025, 22:27 --

А, понял, Вы думаете раз ограничились trial division, то отбрасываем кандидатов могущих дать pqrs. Но это не так, это лишь этот тест не отбросит такого кандидата, он останется под вопросом, но после него могут быть (и будут) другие тесты, более точные. Вопрос не как быстро разложить все 22 числа, а как максимально быстро отбросить все 22 числа если хоть одно не подходит.

[Yadryara]

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

wrest, Дмитрий прекрасно меня понимает.

Задача сложная, этим и интересна. И позиция может меняться по многу раз. В зависимости от практики:

"Ага, раз так быстрее, значит я был неправ и надо делать так".

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

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

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

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

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

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

Какие именно поважнее, Дмитрий уже сказал и код привёл.

[Dmitriy40]

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

wrest, Дмитрий прекрасно меня понимает.

Так подходы разные: я понимаю что, как и зачем надо оптимизировать, а wrest пытается без вникания в тонкости заставить ИИ написать готовый код, просто по описанию что он должен делать. Я пытаюсь оптимизировать алгоритм, он пишет код по готовому алгоритму. И напрягается когда ему такового не дают. Вполне его понимаю. А мы не можем дать пока не понимаем скорости разных вариантов реализации.
Да и сами варианты реализации ещё не придумали. Для меня вон только что стало откровением что проверять на квадраты (но не кубы) может быть выгодно ... Надо тесты проводить.

[wrest]

Dmitriy40
Вам надо тогда наверное сделать какой-то тестовый набор , на котором и обкатывать скорости.
Конечно, если грузить из файла то сначала грузить а потом считать, чтобы не вмешивать файловые операции.
Достаточно большой, чтобы ваши текущие методы работали бы скажем около 30 секунд. Или это будет очень большой файл?
И сформулировать какие-то параметры качества обработки, например нельзя пропустить ни одного подходящего или пропустить не более стольких-то процентов.

-- 02.12.2025, 00:26 --

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

а wrest пытается без вникания в тонкости заставить ИИ написать готовый код, просто по описанию что он должен делать.

Именно так, я не хочу вникать в тонкости паттернологии.

-- 02.12.2025, 00:32 --

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

А, понял, Вы думаете раз ограничились trial division, то отбрасываем кандидатов могущих дать pqrs. Но это не так, это лишь этот тест не отбросит такого кандидата, он останется под вопросом, но после него могут быть (и будут) другие тесты, более точные.

Ну так у вас есть factor(n, 2^14) - им откидывайте легкие числа (с малыми делителями). А трудные откидывайте той же omega_upto()

[Dmitriy40]

wrest
Внимательнее с авторами цитат, последние слова тоже мои.

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

Ну так у вас есть factor(n, 2^14) - им откидывайте легкие числа (с малыми делителями).

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

Например: не искать делители если их уже слишком много - что Вы и сделали в omega_upto().

Другая более менее очевидная идея: поменять порядок обхода циклов foreach и forprime, снаружи не по местам кортежа, а по простым делителям, внутри же по местам кортежа - и потестировать будет ли это быстрее в среднем на большой выборке. Всё же малые делители встречаются довольно часто (по сравнению с очень большими), ведь даже factor(n,2^14) хорошо отфильтровывает (не по одному числу, а кортежи из двух десятков чисел, какое-то да даст причину отбросить кортеж), а ещё меньшие пороги маскируются накладными расходами интерпретатора, возможно после компиляции сами циклы станут сильно быстрее и появится смысл пооптимизировать.

-- 02.12.2025, 02:56 --

Или вот ещё идея (ещё ближе к моим ускорителям на асме).
Не знаю зачем Yadryara выкладывает список чисел, их же легко получить по формуле n=n0+i*m с некими n0 и m (ну потом ещё поделить (n+d-1)/v[d], d=[1..22] чтобы получить именно факторизируемые числа).
А учитывая что она линейная по i, т.е. при i++ каждое следующее n можно получать из предыдущего простым добавлением m, то можно вообще отказаться от делений в factor(n,2^14) - можно просто хранить все остатки по всем простым до 2^14 каждого места кортежа и при i++ выполнять сложение по модулю двух векторов, предыдущих остатков и (m+d)%p для каждого d и p. Вектора будут длинными (1900*22), но зато заменяем медленное длинное деление (n+d)%p на 22 простых сложений по модулю. В PARI даже специальный тип для этого есть, Mod(x,p), их вполне можно складывать. Быстрее это вряд ли будет, но ведь простые у нас маленькие, остатки тоже маленькие, можно чисто на C написать сложение по модулю и будет существенно быстрее чем на PARI с его длинной арифметикой. Вопрос насколько быстрее. И какого размера вектор понадобится для максимальной скорости. У меня на асме примерно это и делается, только там простые до 2^15 и для сложения по модулю используется AVX2 (3 команды за 1.5 такта складывают 16 чисел по модулю, практически 10 чисел за такт), возможно компилятор С умный и сам векторизирует (с AVX2) сложение таких векторов. Скорость асм кода не получится (вот не верю я в качество компиляторов), но будет намного быстрее даже скомпилённого PARI. Если не заставить его не пользоваться длинной арифметикой конечно, как вроде бы Вы умеете (у меня на интерпретаторе не получилось), тогда может быть и не придётся на С ничего писать, обойтись только PARI.

-- 02.12.2025, 03:01 --

wrest
Отдельный вопрос: нельзя ли эти функции уже в скомпилённом виде вытащить и приложить к gp коду. Вроде бы PARI поддерживает загрузку функций из библиотек, та самая install, вдруг это работает и под виндой (только непонятно как скомпилить отдельную функцию) ... Во всяком случае оговорок про *unix only в доке не видел.
Вот не могли сделать нормальную поддержку внешних dll, гады! Как бы всё упростилось.
Может и правда забить на PARI и сделать на том же Питоне ... Правда как там с внешними dll я не в курсе совсем. Но по крайней мере и длинная арифметика, и isprime(), и numdiv() в нём есть.

[Yadryara]

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

Не знаю зачем Yadryara выкладывает список чисел, их же легко получить по формуле n=n0+i*m с некими n0 и m (ну потом ещё поделить (n+d-1)/v[d], d=[1..22] чтобы получить именно факторизируемые числа).

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

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

[wrest]

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

Вроде бы PARI поддерживает загрузку функций из библиотек, та самая install, вдруг это работает и под виндой (только непонятно как скомпилить отдельную функцию) ...

Ну почему непонятно, в гайде есть текст про сборку под mingw. Так что если освоите кросс-компиляцию то наверное можно
Но проще будет таки под линуксом.
Вам же всё равно нужна длинная арифметика, придется или писать или как-то учиться использовать gmp.

-- 02.12.2025, 07:38 --

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

Может и правда забить на PARI и сделать на том же Питоне ... Правда как там с внешними dll я не в курсе совсем.

Так спросите у ИИ :)

-- 02.12.2025, 08:27 --

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

видимо, не вник даже в тот упрощённый код, что я показал выше и не увидел

У вас в коде часть переменных не используется, код не оформлен отступами, комментариев нет.
Аналог письма на бумаге "как курица лапой", то есть расшифровать можно, но затратно
Вы к нему привыкли, и не хотите сделать понятным для других - ну ок, зачем же мне вникать?

[Yadryara]

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

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

У вас в коде комментарии есть. Но я подозреваю, что это именно частное в 4-х местах названо остатком. Зачем??

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

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

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

Насчёт неиспользуемых переменных. Вот есть такая пара векторов:

kdel = [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];  

Видите, аккуратно выписаны один под другим. И пробелы подставлены для выравнивания. Для чего? Именно для того чтобы понятно было, что есть разные понятия и значения у них разные. Наверху количество делителей, а внизу количество различных простых делителей.

И не вводится внизу новое обозначение, потому что это Владимир так обозначил: nu. Видимо, number unical.

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

Ну нафига устоявшиеся термины применять в другом смысле? Уж лучше тогда отдельные словечки выдумывать если обычных слов почему-то не хватает.

[wrest]

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

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

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

-- 02.12.2025, 10:01 --

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

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

А вот так, например, можно было?

/* kdel[i] количество делителей для i-го числа */
/* Далее будем проверять что числа в последовательности имеют ровно 4, 16 и т.д делителей */
kdel = [4,16,16,16,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8]; 

/* nu -- вектор с количеством различных простых множителей для n[i]-го числа */
nu   = [2, 4, 4, 4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3]; 

[Yadryara]

wrest, конечно можно. Но считал, что из контекста обсуждения это прекрасно понятно.

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

install(omega_upto,GGG);

{t0=getwalltime();print;

kdel = [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];  

maxnu = 4;

name = fileopen("Chisla_1.txt");

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

nom++;

t1=getwalltime();

if(omega_upto( n, maxnu, 0) == nu[ (nom-1)%21 + 1],

kpod++;
print1(kpod, ".   ", nom, "     omega_upto = ", omega_upto( n, maxnu, 0), "   ");
\\print(strtime(getwalltime()-t1));
print;

);
);

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

[wrest]

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

Но считал, что из контекста обсуждения это прекрасно понятно.

Ну ок
Тут смотрите как. Мне неинтересны эквиделительные задачи из пентадектлонной темы, в целом.
Я не хочу вникать в алгоритмы формирования "паттернов", что там значат "места" и загадочные (для меня) сообщения типа

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

Ну вот кстати, другие серии пока не колышат. Речь только о 1-1-17-3-10!

Но я мог бы, имея WSL, попробовать делать какие-то мелкие функции на замену factor(n,D); omega(); bigomega(); moebius() и т.п.
Если вам нетрудно сформулировать что вы хотите конкретно от небольшой функции, я могу попробовать их написать при помощи ИИ.
Если трудно -- ок, тогда моё участие для вас неполезно.

[Yadryara]

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

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

И это неминуемо означает, что вы и сообщения Дмитрия во многом не понимаете.

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

Но я мог бы, имея WSL, поробовать делать какие-то мелкие функции на замену factor(n,D) omega() bigomega() и т.п.
Если вам нетрудно сформулировать что вы хотите конкретно от небольшой функции, я могу попробовать их написать при помощи ИИ.
Если трудно -- ок, тогда моё участие для вас неполезно.

Да не парьтесь. В любом случае уже очень полезно.

И насчёт трудно-нетрудно тоже не парьтесь. Всё равно же постепенно начнём понимать друг друга.

Вот ещё пока такие тесты провёл:

omega_upto( n, 4, 0)

1.    2     omega_upto = 1
2.    4     omega_upto = 0
3.    6     omega_upto = 2
4.    8     omega_upto = 0
5.   10     omega_upto = 2
6.   12     omega_upto = 0
7.   18     omega_upto = 0
8.   27     omega_upto = 0

1 ms


omega_upto( n, 4, 1)

1.    2     omega_upto = 1
2.    4     omega_upto = 1
3.    6     omega_upto = 2
4.    8     omega_upto = 1
5.   10     omega_upto = 2
6.   12     omega_upto = 2
7.   18     omega_upto = 2
8.   27     omega_upto = 1

1 ms

Надеюсь, здесь всё понятно. При нулевом флаге в вашей омеге, выбрасываются все степени выше первой.

[wrest]

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

И это неминуемо означает, что вы и сообщения Дмитрия во многом не понимаете.

Как раз нет, Dmitriy40 я понимаю гораздо лучше чем вас

-- 02.12.2025, 10:38 --

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

При нулевом флаге в вашей омеге, выбрасываются все степени выше первой.

Выбрасываются не степени, а несвободные от квадратов числа. Возвращаемый ноль означает "число n не подходит". При флаге s=0 т.е. вызове omega_upto(n,m,0)причин может быть две: 1. количество различных простых множителей больше чем m либо 2. найдены кратные простые множители.
При флаге s=1 функция omega_upto(n,m,1) возвращает количество различных простых множителей без учёта кратности, или ноль если это количество больше чем m. То есть, если задать какое-то большое m (заведомо больше чем может быть количество различных простых множителей в n), то возвращаться будет то же, что возвращает omega(n) в pari/gp и описанная тут омега https://ru.wikipedia.org/wiki/%D0%9F%D1 ... 0%BB%D1%8C но именно омега $\omega (n)$, а не большая Омега $\Omega (n)$

-- 02.12.2025, 11:20 --

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

Другая более менее очевидная идея: поменять порядок обхода циклов foreach и forprime, снаружи не по местам кортежа, а по простым делителям, внутри же по местам кортежа - и потестировать будет ли это быстрее в среднем на большой выборке.

Идея выглядит здравой на первый взгляд.

Но приведу немного отвлечённый пример. Например, вы хотите цикл по trial division, начинающийся не с единицы, а с nextprime(start) то есть с наименьшего простого числа, большего start. Ну на pari вы так и напишете forprime(p=start,...
А на Си вы будете искать начало "руками", то есть начнёте цикл по i с единицы и будете сравнивать i-й элемент таблицы простых со start и когда превысит, при условии что ещё не конец диапазона end, выполнять тело цикла. Чтобы избежать этого ручного поиска, вам надо будет предварител но вычислить положение нужного вам простого и задавать начало и конец диапазона в терминах $\pi (start)$ сразу пропуская поиск nextprime()
Но тогда и требования к функции надо будет предъявить именно такие: диапазон перебора малых множителей задаётся не числами, а порядковыми номерами простых чисел в таблице простых чисел. Тогда перебор между 67 и 2^14 будет задаваться как $start=\pi (67)=19, end=\pi (2^{14})=1900$ и вы сэкономите 19 проверок найдено ли первое простое число диапазона на каждой факторизации

[Yadryara]

wrest, вы уж избыточно подробно объясняете но я совершенно не против. Это гораздо лучше чем недопонять друг друга.

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

2. найдены кратные простые множители.

Это и есть моё неаккуратное, но мне понятное: "При нулевом флаге в вашей омеге, выбрасываются все степени выше первой". То есть если в разложение n входит простое в любой степени выше первой, то такое n выбрасывается. И, в принципе, это пока устраивает.

Допустим я быстро (в 2-3 приёма) проверю разложение с помощью фактора по всем простым до $2^{20}$. Можно ли написать такую омегу, которая проверит дальше, скажем от $2^{20}$ до $2^{27}$ ?

[wrest]

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

Можно ли написать такую омегу, которая проверит дальше

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