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

[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 диск, всё равно ОС не сможет так быстро управлять файлами.