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

[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 с параметрами и обработка вывода.

[Yadryara]

Dmitriy40
У меня вопрос по поводу вашей программы:

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

За три дня наконец написал на асме x64 подсчёт констант HL1 (в один поток).

Прочитал последующие обсуждения. Она несколько раз улучшалась, но так и осталась однопоточной?

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

Сейчас пользуюсь hl1-vc-time.exe от 15 мая прошлого года. Никаких нареканий нет. Разве что крайнее правое число в показе прогресса порой слишком быстро меняется. Стало быть, вывод на экран может тормозить работу.

[Dmitriy40]

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

Она несколько раз улучшалась, но так и осталась однопоточной?

Да.

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

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

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

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

Сейчас пользуюсь hl1-vc-time.exe от 15 мая прошлого года.

hl1-vc-time2.exe существенно точнее:

>gp64 -q n19d252-test4.gp
v=[0, 210]
vC=[1412601623084347443619588493306179650000, 33845225974457624177996288218890240000000, 392594275663605899106904644657257721984750, 2937110655241059526978655281559124546945024, 15928744588945816244500876791400944026199540]
nn=[1, 104, 4131, 98804, 1608195]

>hl1-vc-time.exe 5 0 210
[1412601623084347443e21, 3384522597445762417e22, 3925942756636058993e23, 2937110655241059547e24, 1592874458894581759e25, 6673256111289947458e25]

>hl1-vc-time2.exe 5 0 210
[1412601623084347443e21, 3384522597445762418e22, 3925942756636058991e23, 2937110655241059527e24, 1592874458894581624e25, 6673256111289951608e25]

Как видите у -time2 верные все цифры кроме погрешности менее 1 в последней, в отличии от -time. Конечно погрешность мала у обоих, во всяком случае для малых загрязнений (кажется погрешность -time растёт как корень из количества вариантов в nn[]), но почему бы не пользоваться сразу более точной, скорости у них отличаются процентов на 5, да и то не очень в этом уверен.

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

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

Может. И тормозит. Вопрос - насколько. Вывод происходит фиксированное количество раз (грубо - диаметр^3/8), потому замедление даже в несколько секунд существенно лишь для малых времён, менее минуты, а программа писалась для использования с гораздо более загрязнёнными паттернами, лёгкие можно и на PARI посчитать. И даже для лёгких паттернов, если время увеличивается пусть с 2.5с до 4.7с (как примерно и есть для диаметра 210 из примера выше), то считаю это допустимой платой за показ прогресса.
Кроме того, перенаправление вывода 2>nul работает гораздо быстрее вывода в консоль и позволяет ускорить работу почти до скорости без вывода.
Так что есть выбор, или показ прогресса с общим временем, или чуть быстрее.

[wrest]

Yadryara
У вас сейчас есть готовая инфраструктура (в WSL/Ubuntu) для компиляции и запуска программ не только pari/gp
ИИ, как я заметил, лучше справляется с синтаксисом Си/Си++ чем с pari/gp
Какие-то короткие программы несложных вычислений (например не требующих факторизации или произвольной точности) можно заказывать у ИИ прямо на Си.
Можно в общем-то необязательно в Ubuntu, если Windows вам ближе. Но придётся установить и наладить компиляцию (тут я не очень знаю).

Более того, я попробовал (на планшете) заказывать у ИИ функции, которые вы можете потом вставлять в pari/gp, чтобы например не пользоваться gp2c а делать "напрямую", и с этим ИИ тоже справляется.

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

[Yadryara]

Спасибо.

А я, кстати, запускаю по-другому, программу на PARI из консоли. Вот какой паттерн сейчас считается уже 8-й час:

{print();
t0=getwalltime();

v = [0, 210, 420, 630];
maxcon = 6;
BC =vector(#v+maxcon,k, if(k<#v, 0, prodeulerrat((p^k-k*p^(k-1))/(p-1)^k, 1, nextprime(k+1))));
vMC=vector(#v+maxcon,k, if(k<#v, 0, x=1.0;
forprime(p=3  ,k      ,x/=p*(1-1.0/p)^k);
forprime(p=k+1,v[#v]/2,x/=p-k          );  x));

CC=vector(#v+maxcon,k, 2^(k-1) * vMC[k] * BC[k]);
vC=extern(strexpand("hl1-vc-time.exe ",maxcon,"  ",strjoin(v," ")));

if(type(vC) <> "t_VEC", print(vC); quit);

print;print;
print("v = ",v);

for(i=1,#vC, vC[i]*=CC[i+#v-1]);
print("vC= ", vC, "   ", #vC);

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

[Yadryara]

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

C:\HL1\Asm\CPAP-210>hl1-vc-time.exe 99 0 60
[572556600e0, 4908898560e0, 19058897448e0, 44275879872e0, 68497116236e0, 74303160400e0, 57941831774e0, 32750959046e0, 13353970000e0, 3859063126e0, 764861984e0, 98561550e0, 7586778e0, 302746e0, 4480e0]
Time: 0.080s

C:\FasmNew>48.exe 99 0 60
[57255e4    49088e5    19058e6    44275e6    68497e6    74303e6    57941e6    32750e6    13353e6    38590e5    76486e4    98561e3    75867e2    30274e1    4480]
Time: 18.211s

Как видим, числа-то он научился считать правильно. Но только всё ещё медленно.

Dmitriy40
Как понимаю исходник hl1-vc-time.exe не секрет, по крайней мере для меня. Прошу: если он сохранился, пришлите мне его в личку или на почту. Я сам-то конечно, вряд ли что-то пойму, но попробую ИИ показать. Он грозится многопоточную версию забабахать.

[Dmitriy40]

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

Как понимаю исходник hl1-vc-time.exe не секрет, по крайней мере для меня. Прошу: если он сохранился, пришлите мне его в личку или на почту. Я сам-то конечно, вряд ли что-то пойму, но попробую ИИ показать. Он грозится многопоточную версию забабахать.

Не думаю что получится, но пробуйте, даже интересен результат. Отправил почтой, там 45кБ текста (из-за большой таблицы на почти 5 тысяч чисел).
Но целиком публиковать не стоит.