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

[wrest]

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

Ну так это будет тупой перебор делителей. Это нереально долго.

А, и там ещё другая проблема:

? factor(n,n^(1/3)\1)
***   at top-level: factor(n,n^(1/3)\1)
***                 ^------------------- 
*** factor: overflow in factor [large prime bound].
?

Выше n взято из post1710569.html#p1710569

-- 26.11.2025, 18:43 --

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

Второе, alarm+factor глючит! Когда я писал факторизацию чисел 70+ знаков то на это наткнулся и писал об этом в теме про PARI
(

Печаль... Ну да, тогда только копаться в потрошках например https://github.com/bbuhrow/yafu
Автор там правда не потрудился сделать файл с лицензией, ну предполагать что там MIT (т.е. делай что хошь).

[Dmitriy40]

Yadryara
Вангую ближе к 1e70 вероятность $pqrst$ превысит вероятность $pq$, как превысила вероятность $p$ на 1e38 ...

[Yadryara]

96-ю делителями заинтересовались? Может там надо с другого порога простых начинать. Я паттерны не смотрел

Кстати, вот здесь похоже опечатка:

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

И даже с не влезающей ни в какую память таблицей 67#

Таблица-то не влезающая, только она пока максимум 61#.

[Dmitriy40]

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

Про 67#/61# я долго не думал, написал то число которое фигурирует в коде вашей программы. А так да, таблица 61#. Но она тоже никуда не влезет так что ошибка несущественна.

[Dmitriy40]

Поисследовал вопрос о скорости factor() в PARI в сравнении с YAFU.
Для чисел около 1e58 factor() не укладывается в 1с в примерно 20% случаев. Вызов для них (а их около 250шт для интервала 1e4) YAFU в один поток даёт замедление на 10с из 14м40с, т.е. смысла не имеет, factor() достаточно быстра в этом диапазоне.
Оставшиеся 80% чисел обрабатываются за 7м55с. Так что максимальное возможное ускорение (при бесконечно быстрой факторизации сложных случаев) не превысит 1.9 раза.
Вызов YAFU в 4 потока ускоряет с 14м40с до 12м20с или в 1.2 раза.

Вывод: для чисел до порядка 1e70 нет смысла заморачиваться с улучшением factor().


Как использовать YAFU из PARI (замена fac=factor(n) из показанной выше программы Yadryara):

if(type(fac=alarm(1,factor(n)))=="t_ERROR", \\Ограничим factor одной секундой, времени должно хватить на проверку простоты числа чтобы YAFU не вызывалась для простых
   fac=externstr(strprintf("yafu-x64.exe \"factor(%u)\" -silent -threads 4 |findstr /C:\"=\" |findstr /C:\"*\"",n)); \\Использовать 4 потока
   fac=Set(eval(strsplit(strsplit(fac[1],"=")[2],"*"))); \\Раздербаним строку результата на делители в надежде что никаких ошибок не было
   addprimes(fac);\\Добавим делители в список известных простых
   fac=factor(n,2^10); \\Получим правильное разложение, порог роли не играет, все делители уже известны
   removeprimes(addprimes()); \\Удалим их из списка
);

После этого в fac разложение числа n.

[wrest]

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

Как использовать YAFU из PARI (замена fac=factor(n) из показанной выше программы Yadryara):

Вот, а в идеале было бы вызывать функции yafu из pari, а не через cli. Или, если развитость языка интерпретатора yafu ( https://sites.google.com/site/bbuhrow/yafudocumentation ) позволяет, написать скрипт прямо в нём. Но это конечно хардкорная задача. Кстати насчёт cli - я уверен что нативно, когда и pari и yafu в одной ос (в линуксе ибо нативного pari под windows никто не собирал или мы не знаем о таких попытках) на вызовы даже через cli будет меньше времени уходить. Оба пакета зависят от gmp, например. В нативном случае gmp уже будет в памяти при вызове yafu из pari.

[Dmitriy40]

wrest
Это всё слёзы, показанный вызов YAFU занимает порядка 30мс, а раз уж число не разложилось за 1с, то оно и YAFU не разложится за ту же секунду, а значит накладные расходы меньше 3%. И с ростом чисел этот процент будет быстро падать.
Кроме того, YAFU можно вызывать лишь однажды, для всего списка трудных чисел, перебирать их она умеет сама (-batchfile). Накладные расходы только на запись файла в PARI и обработку результата.

[wrest]

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

Кроме того, YAFU можно вызывать лишь однажды, для всего списка трудных чисел, перебирать их она умеет сама (-batchfile). Накладные расходы только на запись файла в PARI и обработку результата.

А сколько у вас чисел надо факторизовать за какой-то один "квант" ("поток", пакет, запуск). Может вместо факторизации в pari, складывать их в массив, писать в файл(ы) и раздавать разным инстансам yafu? То есть откладывать не только трудные, а все? Или "легкие" числа факторизуются в pari быстрее, чем писать их в файл и читать потом в yafu?
Минимальный порог в одну секунду в alarm() конечно великоват, надо быстрее "сдаваться" если не получилось у factor() в pari. Поскольку pari поставляется в исходном коде, можно просто добавить свою функцию типа alarm_ms() и пересобрать pari с ней, чтобы считать время в мс, но это не будет работать в венде. Хотя это конечно так, фантазии. Заморачиваться вы вряд ли станете (когда созреете на виртуалку с линуксом).

[Dmitriy40]

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

Может вместо факторизации в pari, складывать их в массив, писать в файл(ы) и раздавать разным инстансам yafu? То есть откладывать не только трудные, а все? Или "легкие" числа факторизуются в pari быстрее, чем писать их в файл и читать потом в yafu?

Так можно сделать для тестовой программы выше, которой надо разложить тотально все числа. В рабочих программах надо раскладывать числа лишь до первого неуспеха (когда точно не набирается требуемого количества делителей), ведь в таком случае раскладывать остальные числа кортежа не нужно. YAFU можно заставить считать numdiv, но вот отбрасывать некоторые числа из группы если текущее разложилось недопустимо - вроде нельзя, она не интерпретатор скриптов, а лишь итератор команд.
Это придётся тогда делать хитрее: иметь список из сотни/тысячи кортежей и проверять по одному числу из каждого, те что не подходят выкидывать из списка, оставшиеся проверять следующее число из кортежей, и так далее до опустошения списка или нахождения решения. И всё ради где-то полуторного ускорения ...

Да, отказ от alarm(1,factor()) и передача всех составных чисел в один поток YAFU ускоряет вычисление с 12м20с до 12м10с (т.е. никак) или до 8м25с в 4 потока YAFU.

[wrest]

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

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

А, а я думал в пентадекатлоне принято все раскладывать, по крайней мере Yadryara так вроде делает, видимо дырявые кортежи греют душу или типа того (показывают что вот-вот и успех).

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

И всё ради где-то полуторного ускорения ...

Да, меньше чем на порядок наверное не стоит заморочек.

[Dmitriy40]

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

А, а я думал в пентадекатлоне принято все раскладывать, по крайней мере Yadryara так вроде делает, видимо дырявые кортежи греют душу или типа того (показывают что вот-вот и успех).

Это он просто ещё не добрался до чисел порядка 1e70 и выше, которые могут каждое раскладываться минуты, около 1e50 хватает секунд, когда искали D(36,13) (13 чисел с 36 делителями) там числа были за 1e70 и приходилось использовать как раз alarm+factor чтобы не подвисало на трудных числах. К тому же раскладываются не все, а лишь очень малая часть, которые не отброшены быстрыми проверками (за доли секунд), ведь несколькими секундами на полное разложение можно пожертвовать когда оно не чаще раза в несколько (десятков) минут.

-- 27.11.2025, 23:49 --

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

-- 28.11.2025, 00:19 --

Yadryara
Не знаю нужно ли Вам, но я досчитал таблицу до 1e59.

[Yadryara]

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

Это он просто ещё не добрался до чисел порядка 1e70 и выше,

И не собираюсь добираться. А помните как три года назад я не хотел заниматься количеством делителей больше 12? По этой же причине: не хотел связываться с сильно большими числами. И, позже, всё-таки и другие люди стали заниматься D(12, x). Там ещё и до сих пор есть что считать.

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

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

Недавно писал об этом. И Дмитрий внимательно прочитал. Да, полная проверка делается редко, да, занимает 1-2 секунды, зато считать не так скучно.

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

видимо дырявые кортежи греют душу или типа того (показывают что вот-вот и успех).

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

21-ка в этом плане была удивительным везением. Не только ни одного дро не было в новом поиске, но даже ни одного ранера, а она уже нашлась!!

Так что выше 1e52 пока не смотрю. Это означает, что первый делитель в pqrs никак не больше 10 триллионов.

[Dmitriy40]

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

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

Нет, идея не катит: расчётное среднее время обработки (отбраковки) одного кортежа с числами порядка 1e47 всего 110мкс, даже если их можно отбраковывать по одному числу, то yafu ну никак не сможет проверять 9000 чисел в секунду, она же ещё кучу логов пишет на диск, даже если писать их на RAM диск, всё равно ОС не сможет так быстро управлять файлами.

[Yadryara]

Теперь предлагаю вернуться к вопросу до которого всё не доходили руки:

Чем же ispseudorprime отличается от isprime ? Она же не пропускает какие-то простые ? Просто иногда (очень редко?) в придачу к ним хватает и составные.

Ведь ispseudorprime вроде бы работает ещё быстрее чем factor. И если она так хороша, то может имеет смысл перезаточить там, где всё ещё используется factor.

[wrest]

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

Ведь ispseudorprime вроде бы работает ещё быстрее чем factor. И если она так хороша, то может имеет смысл перезаточить там, где всё ещё используется factor.

Загадочный вопрос. Тест простоты это не то же самое, что разложение числа на множители, одно другим не заменяется.
Если скажем запись числа любой длины заканчивается на 5, я вам мгновенно отвечу, что количество его делителей больше 2, без какой-либо факторизации