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

[Yadryara]

Ну вот на WSL, как понимаю, Убунта это есть WSL, уже второй раз остановка с той же надписью: alarm interrupt after 1,000 ms.

Перезапустил со следующего юнита.

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

Dmitriy40
Истинно говорю вам: да перейдъте уже как-нибудь на WSL или Линукс с minGW...

Ну вот не Дмитрий, так я перешёл. Что скажете теперь?

[wrest]

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

Ну вот не Дмитрий, так я перешёл. Что скажете теперь?

Поздравляю, правильный выбор!

[Yadryara]

Имеете в виду, что сбои пореже происходят чем у Дмитрия? Вот уже третий сбой был. Записываю юниты, которые нужно пересчитывать.

Я имел в виду, может как-то подскажете что-то. Например, как можно уменьшить порог для этого аларма. Раз этак в 10, до 100ms.

Или как учесть то, что проверка делимости на малые простые, например до $2^{20}$, уже была выполнена для всех чисел цепочки? Ведь, как понял, factor об этом не знает и начинает раскладывать заново?

[Dmitriy40]

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

То есть не то что не быстрее, а где-то в среднем на 2% медленнее считались. Да, юниты не ровно те же самые, но они однтотипные.

Ну вот значит не совсем однотипные, раз есть разница. Да и так понятно что даже совсем однотипные могут и будут раскладываться на множители за разное время.
А что разница мала - значит вот это лишнее время проверки сверх 1с затрачивается слишком редко чтобы повлиять на общее время. Т.е. для таких небольших чисел и после таких предыдущих фильтров нет большого смысла ограничивать время факторизации. Если всё у Вас в коде правильно.

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

Кроме того, видимо и у меня возник глюк с алармом к исходу первого часа работы.

Но надпись у Вас другая, у меня писалось user interrupt, что меня и удивило я же не трогал программу, а у Вас alarm interrupt, что более логично, хотя и всё равно непонятно по какой причине. Возможно это из-за разницы в версиях PARI.

DemISdx
Очень похоже на срабатывание неперехватываемого кодом исключения, хотя конструкция alarm() как раз и должна его перехватывать. Т.е. натуральный глюк в коде, обработчик сняли, а таймер его выдающий не остановили. Причём явно не в 100% случаев, а достаточно редко, так что подловить трудно.

[Yadryara]

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

Да и так понятно что даже совсем однотипные могут и будут раскладываться на множители за разное время.

Конечно.

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

А что разница мала - значит вот это лишнее время проверки сверх 1с затрачивается слишком редко чтобы повлиять на общее время.

Конечно. И это было известно заранее. А вот если снизить порог 1сек раз эдак в 10...

Код проверки конкретного паттерна я привёл. Ещё раз пройдусь схематично, в том числе для себя:

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

Ну вот факторизация, как самая медленная операция, специально отдвинута в самый долгий ящик, только в 7-ю и 8-ю очередь выполняется. Я пока пытался пытался оптимизировать только 7-ю.

И всё ещё открытым остаётся вопрос: А так ли нужно перебирать именно по месту с простым? Ведь есть серии и без простых. Я этот вопрос ещё не закрыл окончательно.

[DemISdx]

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

Причём явно не в 100% случаев, а достаточно редко, так что подловить трудно.

Понял.
А если в коде вставить паузу секунд на 10-ть?
В качестве условия, скажем, каждый час или некоторое число вызов (аларма или фактора).
Это исходя из того, что бывают вылеты "достаточно редко"
и в надежде на то, что свой уборщик памяти от процедур "не успевает" все почистить,
отсюда накапливается сегментация в памяти.
Но это, так, пальцем в небо...

[Yadryara]

DemISdx в сообщении #1719429 писал(а):

А если в коде вставить паузу секунд на 10-ть?

Какой код имеете в виду?

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

Если всё у Вас в коде правильно.

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

Кстати, выше я же ещё не отметил нулевую фильтрацию, которая делается ещё до цикла — по КТО. И, кроме этого, ещё до цикла определяется наличие 6-кратного шага.

[Dmitriy40]

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

И всё ещё открытым остаётся вопрос: А так ли нужно перебирать именно по месту с простым? Ведь есть серии и без простых. Я этот вопрос ещё не закрыл окончательно.

Это не вопрос ускорения программы, это вопрос выбора серии паттернов.

DemISdx в сообщении #1719429 писал(а):

Это исходя из того, что бывают вылеты "достаточно редко"

Бывало что потоки работали сутками и неделями без вылетов. А были вылеты и трижды в час (кажется в одном и том же потоке). Одного и того же кода. Так что нет какой либо регулярности.
Отсюда возникает вопрос как проверять что полечилось, сколько ждать если не вылетает, может ведь и неделю проработать, а потом вылететь несколько раз через полчаса ... Ждать же по неделе для каждого варианта костылей ...

Проще отказаться от alarm и если цепочка прошла простые фильтры, то запускать скажем ту же YAFU, она ещё и многопоточно будет раскладывать, правда лишь строго подряд. Я проверял, если numdiv занимает менее нескольких секунд, то замена его на YAFU нерентабельна, слишком часто попадаются легко разложимые числа, для которых встроенный numdiv сильно быстрее вызова внешней проги с обработкой её результатов, проблема лишь как выделить среди всех чисел сложно разложимые. Если бы залезть в исходники PARI, то вариантов сразу несколько возможных, но ... я не могу (не собираюсь разбираться как скомпилить PARI под винду), да и не сильно хочу.

[wrest]

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

Имеете в виду, что сбои пореже происходят чем у Дмитрия?

Я не понял сути/подоплёки/второго дна/намёка в вопросе "Что скажете теперь?", ничего между строк и слов прочесть не осилил, так что ответил как мог, прямо. В моём ответе не было подоплёки/второго дна/намёка/чего-то между строк. То что вы используете WSL и Ubunег в ней для запуска pari/gp и gp2c - считаю что это хорошо, с чем вас и поздравляю.

-- 04.03.2026, 17:50 --

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

Я имел в виду, может как-то подскажете что-то. Например, как можно уменьшить порог для этого аларма. Раз этак в 10, до 100ms.

Полагаю, что никак.

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

Или как учесть то, что проверка делимости на малые простые, например до $2^{20}$, уже была выполнена для всех чисел цепочки?

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

-- 04.03.2026, 18:10 --

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

Если бы залезть в исходники PARI, то вариантов сразу несколько возможных, но ...

В исходники я заглядывал, там всё по теме факторизации поморочено весьма :) Я ж сделал для Yadryara функции omega_upto и omega_range прямо в ядре pari/gp, которые используют закрытый интерфейс и перебирают или до верхнего предела или в диапазоне.
Ну в принципе наверное можно сделать функцию, которая сразу будет перенаправлять факторизационный движок на квадратичное решето минуя перебор малых простых. Только надо ли это (поможет ли)...

-- 04.03.2026, 18:32 --

Мне почему-то кажется, что подход "давайте отложим трудноразложимые числа на потом" какой-то ущербный в том плане, что если "потом" их всё равно надо будет факторизовать, то не стоит и откладывать.
Другое дело, конечно, что "потом" может выясниться, что раскладывать трудноразложимое число не надо так как в цепочке нашлось другое слабое звено из-за которого цепочку отбрасываем. Но если не проверять, до уверенности в проверке, все числа в цепочке, то Yadryara не сможет полноценно коллекционировать дротики, ласточек и прочую фауну

[Yadryara]

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

ответил как мог, прямо.

Вот за это вас очень уважаю.

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

Ну тут ндо уточнить что имеется в виду. Если факторизация делаете перебором простых в словаре, то учесть можно, а если современными методами, то нельзя.

Смотрим когда это делается:

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

4-я фильтрация: проверка всей цепочки по предпростым до $2^{20}$, сбор факторов

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

7-я фильтрация: факторизация только для мест, где факторов ровно на 1 меньше чем надо.
8-я фильтрация: факторизация только для мест, где факторов ровно на 3 меньше чем надо.

4-я фильтрация делается как раз по перебору простых в словаре, начиная, например, с 97, как в последней программе:

mes = lenv - (ostn0a[nompr] + ostma[nompr]*i - ip + lenv - 1) % predp[nompr];

А вот, 7-я и 8-я фильтрации делаются c помощью factor :

if( type(kfnew = alarm(1,factor( (n+ostmes[j]-1)/(v[ostmes[j]]*pro[ostmes[j]]) ) ))

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

Я ж сделал для Yadryara функции omega_upto и omega_range прямо в ядре pari/gp, которые используют закрытый интерфейс и перебирают или до верхнего предела или в диапазоне.

Спасибо ещё раз. Как раз собирался вернуться к этому вопросу и вспомнить что считалось этими функциями.

[Dmitriy40]

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

Другое дело, конечно, что "потом" может выясниться, что раскладывать трудноразложимое число не надо так как в цепочке нашлось другое слабое звено из-за которого цепочку отбрасываем.

Вот в этом и суть давно используемого метода ускорения перебора цепочек - как можно быстрее найти причину отбросить цепочку и перейти к следующей.
Как вариант этого метода: оставляем трудно разложимые числа и цепочки с ними на "совсем потом", в надежде что найдётся цепочка с легче разложимыми числами и даст искомое решение. Мы же не ищем строго минимальное решение, а любое. И можно устраивать "гонки", что произойдёт быстрее, найдётся другая цепочка с решением или доразложатся числа из данной цепочки. Для чисел с ~60 знаками это ещё не столь важно, а вот 80+ цифр именно так и действовал, записывал все трудно разложимые числа (если их оставалось мало в цепочке, 1-2) в отдельный файл и запускал их разложение по мере охоты.

-- 04.03.2026, 19:25 --

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

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

Я имел в виду, может как-то подскажете что-то. Например, как можно уменьшить порог для этого аларма. Раз этак в 10, до 100ms.

Полагаю, что никак.

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

wrest, насколько понимаю, это число 1000 в 194-й строке "(WAITORTIMERCALLBACK)win32_cb_alarm, &arg , s*1000, 0, 0);" файла pari-2.11.0\src\systems\mingw\mingw.c.
Правда не повлияет ли это ещё на кучу других функций я не смотрел.
Хм, и под юниксом возможно и не получится, там в pari_alarm() из pari-2.11.0\src\language\gplib.c вызывается просто alarm(s), в секундах, без пересчёта.

[wrest]

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

4-я фильтрация делается как раз по перебору простых в словаре, начиная, например, с 97, как в последней программе:

Я этого не понял, т.к. не понимаю что значит "для мест" и что значит "где факторов меньше чем надо". Так что пропустил это мимо ушей не вникая. Мы с вами не в теме про мечту, я той терминологии по "места" не понимаю. Просто напоминаю вам, что писать желательно яснее, если вы хотите чтобы было универсальное понимание.

Для меня, в приложении к pari/gp, фильтрация по простым в словаре это использование функции factor(n,D) где D - это верхний предел перебора простых делителей.

-- 04.03.2026, 19:30 --

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

Да ладно, это ж "просто": ни в винде ни в линуксе нет таймера строго на секунду, значит ищем в коде alarm() где первый аргумент превращается в количество тиков имеющихся таймеров и меняем коэффициент пропорциональности.

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

[Dmitriy40]

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

Для меня, в приложении к pari/gp, фильтрация по простым в словаре это использование функции factor(n,D) где D - это верхний предел перебора простых делителей.

Вообще-то фильтрация по словарю простых это ещё и про структуру addprimes(), которая используется примитивами факторизации.

[Yadryara]

wrest
Хорошо. Давайте сначала по терминологии. Я как раз хотел об этом написать.

Здесь у англоговорящих преимущество. Потому что у них есть факторы и дивизоры. И они обозначают этими разными словами разные понятия.

Вы согласны что у числа 123456 всего 3 фактора, но дивизоров аж целых 28 ?

Теперь про места. Вот есть цепочка с одинаковым количеством делителей:

242, 243, 244, 245

Число 242 находится в ней на 1-м месте, 243 — на втором, 244 — на третьем, 245 — на четвёртом месте. Что здесь ещё объяснять про места я пока не знаю. Вроде место в цепочке это простое понятие.

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

Я этого не понял, т.к. не понимаю что значит "для мест" и что значит "где факторов меньше чем надо". Так что пропустил это мимо ушей не вникая.

А раньше вы это прекрасно понимали и в вашей функции эти понятия использовались.
Но не страшно. Заново объясню.

[Dmitriy40]

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

Здесь у англоговорящих преимущество. Потому что у них есть факторы и дивизоры. И они обозначают этими разными словами разные понятия.

В русском тоже разные понятия: "простые делители" и "делители" соответственно.