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

[wrest]

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

Похоже factor выигрывает за счёт Полларда/ECM, не MPQS.
А встроенный MPQS примерно в полтора раза медленнее.

Там мне непонятно. Видимо, ~30мс на вызов уходит на инициализацию или типа того. Не уверен.

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

Но мне полезнее сравнение с YAFU - она многопоточная сама по себе,

Ну это скорее проба возможностей была. Можно ли писать прямо на Си и потом использовать это как внешнюю функцию. Оказалось что можно.

Я как-то последнее время, для форумных развлечений, прошу Qwen-а писать на Си, потому что для pari/gp иногда очень долго написание идёт, постоянные проблемы с синтаксисом. А на Си получается с первого раза, а если не получается - то редко когда из-за синтаксиса.

Для эксперимента, попросил даже написать факторизатор (Поллард), с использованием GMP, чтобы длинные числа считались. В общем, ИИ -- сильная штука. Я так-то Си не изучал никогда, и не писал. Паскаль только, в детстве. И как ни странно, немного ассемблер. Но не х80/86

-- добавлено через 38 минут --

Dmitriy40
Наткнулся тут на веасьма интересную презентацию.
https://www.researchgate.net/profile/Da ... BA0GJawXWw

[wrest]

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

Сподобился прикрутить msieve в pari/gp
Ниже тест. Брались случайные полупростые числа.
Тест на планшете, в один поток.

Попробовал тот же тест, но на стороне фактори9ации pari/gp вместо factor() запускал factorint(n,2+4) то есть без Полларда и без предварительного ECM, и картина стала обратная: pari/gp побеждает почти везде, до размера в 72 цифры, затем быстрее msieve.

Вывод такой От добра добра не ищут. В один поток встроенная в pari/gp факторизация вполне на уровне по скорости до полупростых чисел битностью 240.

[Dmitriy40]

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

Наткнулся тут на веасьма интересную презентацию.

Да, интересное сравнение.
Но особых неожиданностей не заметил.

[wrest]

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

Но особых неожиданностей не заметил.

Ну вот как раз неожиданнгсть с pari/gp
У меня намерилось, что pari быстрее msieve до 72 цифр. А значит, до этой границы pari будет (в однопотоке) по скорости как YAFU или совсем немного медленнее. И, как вы правильно говорите, на сторону стоит смотреть только за многопоточностью.

[Dmitriy40]

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

на сторону стоит смотреть только за многопоточностью.

Не только (далее про YAFU):
оценивает примерно требуемое время (для сложных случаев, когда запустился QS или NFS), да и ECM показывает прогресс перебора кривых с оценкой времени;
можно заставить закончить после нахождения одного делителя (не пробовал);
можно регулировать точку переключения с ECM на QS и на NFS;
для сложных случаев используются файлы на диске вместо памяти (PARI запросто может не хватить памяти для факторизации);
можно запускать сразу для списка чисел (но вытащить результаты будет сложнее), да и обрабатываются они последовательно.

Вообще было бы интересно поискать методы факторизации на GPU (многие методы допускают распараллеливание), пусть даже не самые быстрые. Правда пока для текущих задач вроде не надо. Да и GPU не у всех есть (у меня вот нету).

[wrest]

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

Вообще было бы интересно поискать методы факторизации на GPU (многие методы допускают распараллеливание),

Так в msieve есть же.

[Dmitriy40]

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

Так в msieve есть же.

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

[wrest]

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

можно регулировать точку переключения с ECM на QS и на NFS;

А всё это можно через API?
Эти переключения можно и в msieve сделать, ессно.
Ну а так-то и в pari можно по-множительно искать, что в ECM, что MPQS.

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

оценивает примерно требуемое время (для сложных случаев, когда запустился QS или NFS), да и ECM показывает прогресс перебора кривых с оценкой времени;

Ну это ж если его самого UI запускать, а я-то думал об интеграции и использовании как бибилиотеки в pari/gp, причём для поточной факторизации, где критичны оверхеды на вызовы/инициализации библиотечных функций.

A GNFS это же такое... Нам (в pari) оно зачем? :)

Пока что у меня на примете только gmp-ecm как кандидат вместо паришного ecm, но я уже что-то сомневаюсь, увидев что msieve не даёт ожидаемого прироста. Плюс собсно этот Циммерман который написал gmp-ecm, консультировал и паришников (об этом есть в коментах в исходниках). Всё-таки паришники неплохо сделали, я считаю.

-- добавлено через 2 минуты --

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

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

А, ну это я не знаю. Вряд ли. Этот софт (msieve, yafu, факторизация в пари) весь очень древний, мне как-то показалось что нового не пишет никто.

[Dmitriy40]

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

А всё это можно через API?

Это всё можно через параметры командной строки запуска. Считать ли это за API - вопрос.

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

а я-то думал об интеграции и использовании как бибилиотеки в pari/gp, причём для поточной факторизации, где критичны оверхеды на вызовы/инициализации библиотечных функций.

Такой вариант я не рассматривал. Только вызов готового exe с параметрами и обработка вывода.