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

[wrest]

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

Только я её сознательно не отключал.

Наверное Qwen подкузьмил
В интерпетаторе все параметры можно посмотреть метакомандой \d
Конкретно параметр как много сообщать в консоль о памяти, называется debugmem, его значение можно посмотреть командой \gm

-- 21.03.2026, 16:31 --

Yadryara
В обработке цепочек вроде некому потребля память, по крайней мере у меня не потребляется.
Самое большое это таблицы простых и остатков.
Но у вас же всё в куче там, подготтвка паттерна с КТО и прочее - там наверное память и уходит.

-- 21.03.2026, 16:34 --

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

То есть все фильтрации, начиная с 4-й, для всё меньшего количества предпростых ожидаемо выполняются хуже, кроме самой последней. Чудеса какие-то...

Этот абзац непонятен.

[Yadryara]

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

В обработке цепочек вроде некому потребля память,

"Неприличными словами не выражаться!"

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

Этот абзац непонятен.

Ну вот новая стата подоспела:

16   [0, 6967296, 2634638, 151997, 4555, 271, 0]                9min,    109 ms
17   [0, 6967296, 2634638, 110429, 2673, 184, 0]                8min, 58,533 ms
18   [0, 6967296, 2634638,  81282, 1556, 124, 1]               10min,  1,922 ms
19   [0, 6967296, 2634638,  60716,  903,  86, 1]               12min,  2,107 ms
20   [0, 6967296, 2634638,  45801,  533,  66, 1]               15min, 11,192 ms

21-ю степень 2-ки уж не стал смотреть и так понятно что будет.

Что тут непонятного...

Чем больше предпростых тем лучше фильтрация на этом 4-м этапе. Наглядно это и видим в 4-х элементах векторов: количество оставшихся цепочек всё меньше и меньше: 151, 110, 81, 60, 45 тысяч. И дальше этот статус-кво вроде сохраняется. А вот самая последняя фильтрация ведёт себя ровно наоборот — лучше фильтрует при меньшем количестве предпростых. И этому есть объяснение.

Ещё буду детально разбираться.

Здорово, что и время сильно снижается при переходе от 20-й степени к 16-17-й.

[wrest]

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

Что тут непонятного...

Ничего. Какие-то столбцы цифр...
Что такое "предпростое"?

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

количество оставшихся цепочек всё меньше и меньше: 151, 110, 81, 60, 45 тысяч.

А что такое "151, 110, 81, 60, 45 тысяч." - это вошло/вышло? Откуда/куда?
Суммы по векторам разные везде..

-- 21.03.2026, 18:37 --

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

Здорово, что и время сильно снижается при переходе от 20-й степени к 16-17-й.

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

[Dmitriy40]

Это просто значит что таблица простых слишком велика и тратит слишком много времени без ощутимого эффекта - выгоднее не таблицу увеличивать, а пропускать больше цепочек на следующие этапы проверок.

-- 21.03.2026, 19:17 --

Функция времени работы от размера таблицы имеет минимум, и при уменьшении и при увеличении размера время растёт, при уменьшении из-за ухудшения фильтрации и более частого запуска следующих проверок, при увеличении из-за слишком длительного перебора таблицы. Судя по данным оптимум около 2^16..17.
Разумеется оптимум зависит от вида/качества дальнейших проверок, чем они лучше и быстрее, тем меньше нужна таблица.

[Yadryara]

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

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

Что тут непонятного...

Ничего.

Ничего непонятного. То есть всё понятно.

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

Что такое "предпростое"?

Предвычисленное простое. Если в крайнем левом столбце 20, значит степень 2-ки 20-я. Значит предпростые, грубо говоря, берутся до миллиона.

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

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

количество оставшихся цепочек всё меньше и меньше: 151, 110, 81, 60, 45 тысяч.

А что такое "151, 110, 81, 60, 45 тысяч." - это вошло/вышло? Откуда/куда?

Мне не очень нравится вошло/вышло. Хотя можно и так.

Вот есть запись:

16   [0, 6967296, 2634638, 151997, 4555, 271, 0]

Если в крайнем левом столбце 16, значит степень 2-ки 16-я. То есть 4-е значение 151997 — это количество цепочек оставшихся после 4-й фильтрации (до $2^{16})$.
4555 — количество цепочек оставшихся после 5-й фильтрации.
271 — количество цепочек оставшихся после 6-й фильтрации.
0 — количество цепочек оставшихся после 7-й фильтрации.

Далее в том же интервале с другой настройкой:

17   [0, 6967296, 2634638, 110429, 2673, 184, 0]

Если в крайнем левом столбце 17, значит степень 2-ки 17-я. То есть 4-е значение 110429 — это количество цепочек оставшихся после 4-й фильтрации (до $2^{17})$.
2673 — количество цепочек оставшихся после 5-й фильтрации.
184 — количество цепочек оставшихся после 6-й фильтрации.
0 — количество цепочек оставшихся после 7-й фильтрации.

Количество цепочек оставшихся после 4-й фильтрации всё меньше и меньше: 151 и 110 тысяч соответственно.


А, ну вот, Дмитрий понял правильно.

[wrest]

Мои данные, на миллионе цепочек.
"Терапевтика" отбрасывает 727 857, на этап проверки по таблице простых остается 272 143
Из этих 272 143, в зависимости от величины таблицы, отбрасывается:

2^  отброшено прошло дальше 
24  272127         16
23  272126         17
22  272120         23
21  272103         40
20  272090         53
19  272064         79
18  272029         114
17  271949         194
16  271831         312
15  271617         526
14  271178         965

[Dmitriy40]

wrest
По этим данным оптимум не определить - рассмотрим две крайние ситуации:
1. дальнейшие проверки моментальны - оптимум будет вообще без таблицы;
2. дальнейшие проверки очень долгие или отсутствуют - оптимум будет при максимально большой таблице.
При реальных временах следующих проверок оптимум будет где-то в промежутке, но в зависимости от соотношения времён проверки таблицы и следующих.
Предположительно около 2^16..18.

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

[wrest]

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

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

Согласен, но как я говорил, из-за тротлинга не очень доверяю времени.
Получилось так:

2^ скорость цепочек в секунду
24 220994
23 200722
22 201857
21 204834
20 197472
19 192566
18 205212
17 193610
16 202020
15 191204
14 172087

тут общая скорость - включая все стадии отсева (но не включая формирование паттерна)

[Dmitriy40]

Ну если не обращать внимания на выбросы, то вижу скачок скорости на 2^15 и потом в общем почти стабильно.
Считать ли скорость при 2^24 выбросом это вопрос, может и правда следующий скачок. Или ошибка измерений.
Если про 2^24 забыть, то нет большого смысла делать таблицу больше 2^15. Хотя если ничему не мешает, то можно и максимально большую, раз уж до торможения не добрались.

С другой стороны, при достаточно хорошей фильтрации размер таблицы начиная с некоторой пороговой величины роли уже не играет - она никогда не перебирается до конца, всегда обрывается до того. Но тогда и последующие проверки уже не нужны. Если не точно всегда, а почти всегда, но следующие проверки не слишком медленные и уже почти не влияют на общее время - тоже нет смысла увеличивать размер таблицы. Что похоже и наблюдаем.
И нет, это не противоречит моим предыдущим словам про минимум времени - это оптимизация по двум разным переменным и неудивительно что результат разный.

[wrest]

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

Хотя если ничему не мешает, то можно и максимально большую, раз уж до торможения не добрались.

Торможение там наступает на создание таблицы. Но это если проверять миллион. А если проверять 10 миллионов, то создание таблицы влияет в 10 раз меньше :)

В таблице в среднем одна проверка на уепочку на простоту, с ключом 1. А дальше 4 проверки на простоту на цепочку, с ключом 0.

В общем я подозреваю, что зависит и от паттерна, если числа большие, то проверке по таблице это пофиг, а вот полларду и mpqs уже нет, так что имеет смысл все-таки вызывать их поменьше если числа будут расти.

Я считаю, что модулярный метод проверки по таблице - наиболее быстрый из нам известных (для pari) и он реализован.
У меня там остались ещё счётчики это, но это скорее всего не тормозит.

Главный драйвер ускорения - уменьшение количества проверок на простоту.
Например "терапевтика" вообще не использует ispseudoprime, и уменьшает общее количество проверок в 4 раза, с 1,1 проверки на цепочку до 0,28

Ну то есть - скорость примерно обратно пропорциональна количеству проверок на простоту (а время - примерно прямо пропорционально).

Убыстрить ispseudoprime мы уже не можем. Значит, надо сокращать количество проверок.

-- 21.03.2026, 22:40 --

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

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

Ну нет конечно, всегда будут числа с тремя множителями скажем не менее 28..32 бит каждый, до которых вы перебором за достойное время не доберётесь. Именно поэтому существует метод Полларда и прочие.

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

[Dmitriy40]

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

Ну нет конечно, всегда будут числа с тремя множителями скажем не менее 28..32 бит каждый, до которых вы перебором за достойное время не доберётесь.

А это может оказаться неважным - так как все цепочки отбросятся по другим местам и упираться в сложную факторизацию не придётся. Я именно это и имел в виду, что таблица может зарубить все цепочки (ну кроме решения понятно). Мы же не отдельные произвольные числа проверяем, а комплект из них в виде цельного объекта - цепочки/кортежа.

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

Для "терапевтики" и проверки по таблице простых, размер числа в 50 разрядов или 70 роли почти не играет, как мне кажется.

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

[wrest]

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

А это может оказаться неважным - так как все цепочки отбросятся по другим местам и упираться в сложную факторизацию не придётся. Я именно это и имел в виду, что таблица может зарубить все цепочки (ну кроме решения понятно).

Конечно, ну не просто таблица, а ещё доп. проверка на недобор (на перебор делается проверка ещё в табличной части). В том (вашем, со страницы 24) паттерне который кручу я, не в каждом миллионе цепочек доходит до факторизации сверх табличной. Но иногда - доходит.

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

Из мыслей у меня тут такая.
Мы сейчас вычисляем остаток от деления последнего числа в цепочке на простое из таблицы. И если остаток меньше чем длина таблицы, то сразу узнаём, что в цепочке есть число, кратное этому простому, и где это число расположено в цепочке. Нам помогает то, что простое больше чем длина цепочки, и значит не больше одного числа в цепочке может на него делиться.
То есть, мы проверяем строку из например 21 последовательного числа.
Затем следующую строку и так далее.
Но мы можем проверять и столбец. Представим например, что у нас есть таблица, где строки это цепочки,и строк миллион. Это таблица с 21 колонкой (столбцом) и миллионом строк.
А почему бы нам проверять не построчно, а поколоночно? Чувствую что идея плохая, но что-то зацепилась в голове.