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

[wrest]

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

Здесь можно что-то сделать с r (которое в данном примере равно nd) или оставить пустым, это выполняется НЕ параллельно

Я вот это не понимаю. И я у себя в примере написал не так, как вы. В хелпе написано:

Цитата:

expr2 is evaluated sequentially on each r as it appears.

Откуда я делаю такой вывод: параллельно запущены несколько итераций, результаты начинают появляться по мере окончания вычислений, в r, и соответственно в expr2 можно эти результаты вылавливать. Так именно это нам и надо: вылавливать результаты факторизации по мере их появления.
То есть в expr1 вы что кладёте, при чем последовательно одно за одним, оно там варится и появляется по мере готовности в r, который вы можете обработать в expr2.

[Dmitriy40]

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

Так именно это нам и надо: вылавливать результаты факторизации по мере их появления.

Можно и так.
А можно сразу параллельно проверить результат факторизации (пока поток ещё не оборван другим) и выдать "на гора" лишь флаг что надо оборвать все остальные потоки, или не выдавать флаг, а сразу взять и оборвать через error, как и сделано.
По идее результат факторизации нам не нужен - если ошибки не произошло и next не сработало, значит все числа подошли и они все равны 192 или сколько там требуется и программу можно продолжить дальше и вывести найденное в лог и запустить фейерверк. Вопрос получения приближений опускаю.
expr2 выполняется всегда строго однопоточно, даже если все потоки parfor завершатся строго одновременно. Порядок выполнения итераций в expr2 недерминирован, да, но они гарантированно не перекрываются, строго друг за другом, т.е. фактически однопоточно, не параллельно.

[wrest]

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

Порядок выполнения итераций в expr2 недерминирован, да, но они гарантированно не перекрываются, строго друг за другом, т.е. фактически однопоточно, не параллельно.

И что? Мы же в expr2 факторизацией не занимаемся...

[Yadryara]

Спасибо, господа.

Как понимаю, вы друг с другом не согласны как делать. Так что я пока тем более не понимаю как это адаптировать к существующему коду. Прошу не забывать, что в нынешнем коде проверки выполняются уже после многих-многих других (я приводил перечень фильтраций), в которых отбрасывание цепочки целиком происходит по next(2).

[Dmitriy40]

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

И что? Мы же в expr2 факторизацией не занимаемся...

Да ничего, говорю же, можно и так и так и ещё как-нибудь. Мне показалось излишним протаскивать количество делителей наружу из многопотока, ведь достаточно лишь сгенерить ошибку, что можно делать и параллельно.

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

Как понимаю, вы друг с другом не согласны как делать.

Нет, мы согласны. Можно и так и так. Вопрос удобства и понятности. Работать должны оба варианта. Ну с учётом что у меня PARI вываливается в винду в обоих вариантах, точная причина чего так и непонятна.

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

Так что я пока тем более не понимаю как это адаптировать к существующему коду. Прошу не забывать, что в нынешнем коде проверки выполняются уже после многих-многих других (я приводил перечень фильтраций), в которых отбрасывание цепочки целиком происходит по next(2).

Я же привёл практически готовый код (который собственно функционально идентичен коду wrest по указанной им недавно ссылке), он заменяет цикл for(d=0,19, if(numdiv(n+d)<>192, next(2)));, next(2) там заменено на next потому что нет внутреннего цикла проверки (он весь внутри iferr и сквозь него прорубаться уже не нужно).

[Yadryara]

А, если согласны, тогда хорошо, посмотрю более внимательно. Пока, без parfor, у меня вывод такой:

[1, 2, 6, 7, 10, 12, 13, 16, 18, 20]   10

2.  Потрачено 5 ms   Факторов слишком много
15621763   614813194568884725330347254101670326647553073      9604466014828004353430781511277071747020658636327699


[3, 12, 13, 16, 20]   5

3.  Потрачено 31 ms   Факторов слишком много
52245241   587161053329492749239640497869489499677      30676370737013201091777584564551465457594287157


[1, 2, 3, 6, 10, 12, 13]   7

1.  Потрачено 3 ms   Факторов слишком много
3803347   4300410858578223834945217914392653029263656001      16355954737740911887967389719051553720890838260435347


[1, 2, 3, 4, 5, 6, 7, 15, 17]   9

1.  Потрачено 37 ms   Факторов слишком много
1070462957   324170343003915922075348569973531174558069      347012343943676100524159207019587592849113709950033


[1, 2, 3, 13, 16, 20]   6

1.  Потрачено 17 ms   Факторов слишком много
1283289083   9562837968966140959742411514263750271171151      12271885568072141490276579188348169505632227702844533


[1, 2, 4, 7, 15, 16, 18, 20]   8

1.  Потрачено 39 ms   Факторов слишком много
1879166687   4050586246506620101197601367239182631753367      7611726737255610619135101293621525162699915666485129


[1, 3, 4, 5, 7, 8, 9, 10, 13, 15, 16, 20]   12

  ***   the PARI stack overflows !
  current stack size: 888000000 (846.863 Mbytes)
  [hint] set 'parisizemax' to a nonzero value in your GPRC
  ***   Error in the PARI system. End of program.
yadryara@DESKTOP-QPP2F5P:~/Parfor2$

Как видим, в списке на проверку уже не 20 мест, а гораздо меньше.

В первом случае 10 мест, они перечислены. При проверке уже 2-го места, на которую было потрачено 5 ms, выясняется, что факторов уже слишком много. То есть это попросту означает, что кофактор, то есть число 614813194568884725330347254101670326647553073 — составное.

Во втором случае 5 мест, они перечислены. При проверке уже 3-го места (то есть 1-го в списке из 5-ти), на которую было потрачено 31 ms, выясняется, что факторов уже слишком много. То есть это попросту означает, что кофактор, то есть число 587161053329492749239640497869489499677 — составное.

Ну и так далее. На 12 мест отчего-то уже не хватает памяти. Не только 800М, но даже и 2-х Гигов.

[Dmitriy40]

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

На 12 мест отчего-то уже не хватает памяти. Не только 800М, но даже и 2-х Гигов.

Какая-то проблема в коде (где-то память не освободили), так быть не должно.

[Yadryara]

Я пока грешу на алгоритм Полларда. Ведь именно он у меня здесь работал. Разбираюсь как он работает. Вроде у него бывают зацикливания...

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

Тут нужны предположения о распределении времён факторизации.

Здесь два контр-аспекта.

С одной стороны, чтобы быстро отбросить цепочку, нужно чтобы частное имело не меньше 3-х факторов, а чем больше число, тем в среднем больше у него и факторов.

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

Какими по величине будут числа, заранее примерно известно. Вот, кстати, в примере выше виден диапазон чисел, для которых надо было найти наименьший фактор, 47-53-значные:

9604466014828004353430781511277071747020658636327699
30676370737013201091777584564551465457594287157
16355954737740911887967389719051553720890838260435347
347012343943676100524159207019587592849113709950033
12271885568072141490276579188348169505632227702844533
7611726737255610619135101293621525162699915666485129

Я пока склоняюсь к тому, что числа надо брать поменьше, то есть проверять начиная с самого маленького.

[wrest]

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

Пока, без parfor, у меня вывод такой:

По этому выводу, выходит что уже и так всё достаточно быстро работает.
Для замера нужны какие-то времена навроде десятка секунд, чтобы видеть как они уменьшаются.
То есть проверять какую-то пачку цепочек с общим временем проверки десяток секунд, менять алгоритм, брать ту же пачку и смотреть как изменилось время...
Без отладочной печати ессно, потому что это тоже время.

-- 12.03.2026, 08:27 --

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

отчего-то уже не хватает памяти. Не только 800М, но даже и 2-х Гигов.

Это плохо. Чтобы утекло много памяти, тоже нужно время.

[Yadryara]

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

По этому выводу, выходит что уже и так всё достаточно быстро работает.
Для замера нужны какие-то времена навроде десятка секунд, чтобы видеть как они уменьшаются.

Конечно. Я же ведь как определил, что выигрыш от прерывания по таймеру всего лишь 11-12% ? Тесты проводились для одних и тех же наборов чисел. Если был лимит в 1 секунду, то счёт длился 117 секунд, а если был лимит 0.13-0.16с, то счёт длился 104-105 секунд.

[wrest]

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

Если был лимит в 1 секунду, то счёт длился 117 секунд, а если был лимит 0.13-0.16с, то счёт длился 104-105 секунд.

Это, ессно, время на все фильтрации в сумме, верно?

[Yadryara]

Это не просто фильтрация всех мест, которые проверены до отбрасывания, это итоговый результат и по всем предыдущим фильтрациям:

1-я фильтрация вне цикла по i: КТО и терапевтика по 2, 3 и 5.
2-я фильтрация: остальная терапевтика.
3-я фильтрация: проверка всей цепочки по предпростым до $2^{20}$, сбор факторов
4-я фильтрация: если факторов уже стало сколько надо, проверка по псевдопрайм для этих мест
5-я фильтрация: остались только места, где факторов строго меньше чем надо, проверка по псевдопрайм для этих мест.
6-я фильтрация: факторизация только для мест, где факторов ровно на 1 меньше чем надо.

Оптимизировалась по таймеру только 6-я фильтрация.

Причём это было ускорение именно благодаря 6-й фильтрации, потому что до 7-й фильтрации (факторизация только для мест, где факторов ровно на 3 меньше чем надо) в проверяемых цепочках дело обычно ни разу не доходило — все отбрасывались не позже чем после 6-й.

В некоторых тестах был один случай, когда отбрасывание было уже после 7-й фильтрации.

[wrest]

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

Оптимизировалась по таймеру только 6-я фильтрация.

А если бы 6-я фильтрация работала мгновенно, как бы это повлияло на итоговый результат?

[Yadryara]

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

А если бы 6-я фильтрация работала мгновенно, как бы это повлияло на итоговый результат?

Разыскал ту, теперь уже несколько старую программу. Сделал переход к следующей цепочке сразу после 5-й фильтрации — счёт продлился 71 секунду.

То есть 6-я фильтрация добавляла в копилку 117 - 71 = 46 секунд. Из этих 46 секунд 12 удалось скинуть за счёт точного тайминга. То есть ускорение всего счёта было на 11%, а ускорение именно 6-й фильтрации, к которой и применялся этот точный тайминг — на 35 %.

[wrest]

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

То есть 6-я фильтрация добавляла в копилку 117 - 71 = 46 секунд. Из этих 46 секунд 12 удалось скинуть за счёт точного тайминга. То есть ускорение всего счёта было на 11%, а ускорение именно 6-й фильтрации, к которой и применялся этот точный тайминг — на 35 %.

Ага, ясно. Ну тогда бороться за 6-ю фильтрацию имеет прямой смысл, в т.ч. и parfor-ом.