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

[wrest]

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

Мне думается при столь небольших числах (порядка 60 знаков) оптимизировать последнюю фильтрацию не имеет смысла, пусть проверяет хоть всё заново, это по любому доли процента времени проверки

Тут надо мерить. Первые фильтрации это микросекунды, а последние - сотни миллисекунд.
Я на em3() видел заметное падение общей скорости в зависимости от количества попавших на финальный numdiv цепочек. От 1 до 6 процентов на каждую прошедшую из миллиона. (0-3 прошедших, см post1711836.html#p1711836 )

-- 17.03.2026, 19:12 --

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

А если проверять только недоразложенные места, то единицы секунд и процент-два общего времени. Ну и зачем её оптимизировать? Лучше оптимизировать предыдущие проверки, чтобы чисел вываливалось меньше при том же темпе проверок.

Тут я согласен, конечно. Но статистику надо бы собрать ясную, т.к. что пишет Антон -- непонятно.

Я вообще, в практическом смысле, не догоняю зачем нужны две доп. фильтрации после проверки по таблице простых - у меня через таблицу проскакивало довольно мало (0..3 промилле).
Но раз надо так надо, теория понятна

[Dmitriy40]

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

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

Тут вопрос не в процентах, а в скорости, если их 1 штука в час, то да, ничего больше не нужно, если же их 1 штука в секунду, то надо фильтровать ещё, так как при записи в лог будет сделан медленный numdiv, который займёт пусть 5с на цепочку и значит оно и будет тормозить весь процесс, а хотелось бы чтобы оно почти не влияло, значит нужно чтобы до этого доходило мало цепочек (в час, не в процентах!). Т.е. речь о том чтобы медленный финальный numdiv занимал доли процента времени, а учитывая что он занимает не в процентах, а в секундах, надо чтобы ему оставалось поменьше цепочек, т.е. лучше фильтрацию.
0.3% это очень много, надо на пару порядков меньше.
Понимаете, если 5с проверки цепочки (для записи в лог) будут выполняться 0.2% раз, значит скорость составляет не выше 5с/0.2%=2500 цепочек в секунду, это вообще ни о чём. Вы чуть выше сослались (про n0 и m) на мой код, который проверил 100000 цепочек за 5с (включая и накладные расходы на получение этих 10К цепочек), это 2e4 цепочек в секунду, в 8 раз быстрее. И это было до всех оптимизаций, сейчас надеюсь раз в 10 быстрее (сорян, не следил за достигнутой скоростью). Так что нет, фильтрация 0.3% совсем не устраивает, надо намного лучше.
И чем больше числа, для других паттернов, тем дольше работает финальный numdiv и тем лучше должна быть фильтрация до него.

[wrest]

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

0.3% это очень много, надо на пару порядков меньше.

Ой, это я не то написал. 0..3 на миллион. В среднем 1 на миллион.

-- 17.03.2026, 21:12 --

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

И это было до всех оптимизаций, сейчас надеюсь раз в 10 быстрее (сорян, не следил за достигнутой скоростью)

Ну я как написал сюда так ничего и не делал больше, считая что свою миссию выполнил, на 4 ядерном ноутбучном проце:

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

В общем, результат теперь, после компиляции, в многопоточном режиме 230 тыс цепочек в секунду в сумме. 8 миллионов за 35 секунд.

Однопоточно вот уже и не помню, наверное около 80..90 тыс в секунду.

[Dmitriy40]

Ну вот, пусть 2млн за 35с в один поток.
И если, подчёркиваю, если numdiv для всей цепочки занимает в среднем 5с (очень навскидку), то для 2 цепочек за 35с (фильтрация 1млн:1) это составит 10с дополнительно к 35с. Многовато. Фильтрацию неплохо бы ещё улучшить.
А если как у Антона (если я правильно понял) 11 цепочек в час, то добавка 55с к часу - уже хорошая фильтрация и дальше её улучшать пока не обязательно.
Вроде простая же оценка стоит или нет.

[wrest]

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

Вроде простая же оценка стоит или нет.

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

[Dmitriy40]

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

И дело не только в собсно ispseudoprime, а ещё в том, что там делается одно длиннное деление, два длинных умножения и длинное сложение для вычисления остатка(частного), которое и проверяется на простоту).

Не вполне понимаю о каком именно куске кода Вы говорите, но если всё это делается вместе с ispseudoprime, то и наплевать: по сравнению с двумя-тремя сотнями длинных делений внутри ispseudoprime это всё слёзы.

[Yadryara]

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

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

Плохо постарался, можно и нужно ещё усилить:

__________________________________________________________________________
Дано.
Число $n$ не делится нацело ни на одно простое от $0$ до $2^{20}$.
Реализация алгоритма Полларда.
Если эта реализация для числа $n$ возвращает в качестве 3-го параметра число длиной не более 12-ти десятичных знаков, то это число простое.
__________________________________________________________________________

И вот пока не вижу как это можно опровергнуть.

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

Но статистику надо бы собрать ясную, т.к. что пишет Антон -- непонятно.

Что именно непонятно?

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

№   Коротких  Исходное число                         Итераций  Длина    Факторизация фактора
1.    3676    100000000000000000000000000000000223287   97065   13   Mat([2966720871703, 1])
2.    4427    100000000000000000000000000000000268767   44126   13   Mat([2164294909991, 1])
3.    5776    100000000000000000000000000000000349927   73945   13   Mat([5267656595417, 1])
4.    7418    100000000000000000000000000000000453097   93394   13   Mat([1621324922741, 1])
5.    9265    100000000000000000000000000000000565009   86026   13   Mat([3424302652637, 1])
6.    12357   100000000000000000000000000000000754939   74940   14   Mat([14349373861891, 1])
7.    13896   100000000000000000000000000000000853807   85264   13   Mat([1583839892699, 1])
8.    18251   100000000000000000000000000000001116811   92904   13   Mat([2219594942177, 1])
9.    24151   100000000000000000000000000000001479361   97799   13   Mat([2343976822633, 1])
10.   26486   100000000000000000000000000000001623943   89336   13   Mat([1157899770101, 1])
11.   28184   100000000000000000000000000000001723681   93778   13   Mat([1367693980837, 1])
12.   29298   100000000000000000000000000000001793361   32514   13   Mat([2041467347729, 1])
13.   30675   100000000000000000000000000000001876693   22676   14   Mat([17257992311057, 1])
14.   31086   100000000000000000000000000000001900453   70678   14   Mat([23416050988783, 1])
15.   32468   100000000000000000000000000000001985991   21132   14   Mat([23728770249749, 1])
16.   32570   100000000000000000000000000000001992157   36205   13   Mat([1315466945341, 1])
17.   33714   100000000000000000000000000000002061051   63101   13   Mat([1483600372361, 1])
18.   35723   100000000000000000000000000000002181853   85174   13   Mat([1001867741053, 1])
19.   35798   100000000000000000000000000000002186023   86676   13   Mat([3760264823209, 1])
20.   36104   100000000000000000000000000000002206281    1245   14   [1533379, 1; 13896739, 1]
21.   36916   100000000000000000000000000000002256421   91784   13   Mat([5076891189661, 1])
22.   37431   100000000000000000000000000000002290047   93533   13   Mat([2939434015601, 1])
23.   40272   100000000000000000000000000000002464399   75586   13   Mat([1776466468193, 1])
24.   42818   100000000000000000000000000000002618209   86712   14   Mat([90426022937963, 1])
...
74.  153968   100000000000000000000000000000009422101   29299   13   Mat([1284250309063, 1])

Интервал —
10 миллионов. Из них примерно
400 тысяч чисел не делятся на простые до 2^20. Из них
163528 факторов найдено алгоритмом Полларда. Из них
74 длинных фактора. Из них
1 составной.

163 тысячи факторов найдены. И все как один меньше частного.

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

[Yadryara]

wrest, чтобы вам было понятно, неплохо бы начать с самого начала.

Необязательно конечно. Можно сразу взять количество делителей из топ-3: 24, 48 или 96.

Я рекомендую 24 делителя, как самый простой вариант. Не бежим впереди паровоза. Попробуйте программно самостоятельно найти цепочку, которая содержит два подряд числа с 24-ю делителями, D(24, 2).

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

Постепенно в голове возникнет выстраданный порядок как и что надо делать.

И, чем чёрт не шутит, возможно придут какие-то идеи, которые не пришли в голову другим.

Ведь рекорды продолжают падать (в том числе и в этом году!) не потому, что компы стали сильно быстрее чем 3-4 года назад, а потому что понимание приёмов решения задач участниками весьма и весьма неидеально, даже если они не первый год ими занимаются.

[wrest]

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

Не вполне понимаю о каком именно куске кода Вы говорите,

В последней инкарнации функции em3() с 29 страницы темы логика такая.
Мы идём по простым числам с 59 до 2^20
Вычисляем остаток от деления последнего числа в цепочке на очередное простое. Если остаток меньше количества чисел в цепочке, значит какое-то число делится на текущее простое. Выясняем какое и накапливаем для него количество простых делителей и их произведение. Проверяем, не накопилось ли уже достаточно простых делителей. Если накопилось, то вычисляем остаток(частное) с учётом множителей которые мы заложили в паттерн.
И вот далее проверяем остаток(частное) на простоту. Если остаток (частное) составной, то у нас перебор и отбрасываем цепочку.
Участок кода, отсюда post1711836.html#p1711836 вот этот:

      nf[d]++; \\ на i-е простое разделился d-й член цепочки накопим по нему омегу
      nn[d]*=pr[i]; \\ и накопим по нему частное
      \\Если уже перебор множителей, то отбрасываем всю цепочку
      if(nf[d]==nu[d],q1++;if(!ispseudoprime((n0+2*k*m+d-1)/(v[d]*nn[d]),1), next(2)));

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

-- 18.03.2026, 09:00 --

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

чтобы вам было понятно, неплохо бы начать с самого начала.

Не-не, я хочу сосредоточиться на теме где мы находимся сейчас: ускорении имеющихся подходов. И не очень хочу вникать в тему-мечту где обсуждается паттерностроение т.к. там вроде нечего ускорять.
Для меня задача звучит как: имеются от 20 до 30 последовательных чисел ("цепочка"), известно что каждое из них делится на какие-то числа из "паттерна" (т.е. известен паттерн), нужно как можно быстрее отсеять весь набор если какое-то из этих 20-30 имеет больше или меньше делителей чем заданное количество 48,96 и т.п.). И расширение этой задачи: задан набор из большого количества (~миллион) цепочек, первые члены составляют арифметическую прогрессию с известным шагом.
Текущая скорость проверки составляет примерно 90 тыс. цепочек в секунду в однопоточном и 220 тыс. в секунду при 8 потоках на 4 ядрах (на моём ноутбуке).

[wrest]

Насчёт новых идей.

Кажется, что при подсчётах переполненности делителями, надо использовать "настоящую" формулу количества делителей, с учётом степени простого множителя, а не предполагать свободу от квадратов.
Накапливать сигму-ноль (количество делителей, numdiv) а не омегу (количество различных простых множителей).
Соответственно, если число в цепочке разделилось на простое, то проверить не разделится ли ещё, и при том возможно, несколько раз, на то же простое. После чего проверять, является ли накопленный numdiv делителем 48,96 (или что мы ищем).
Ещё я пока не понял, есть ли всё-таки гарантия, что простых множителей по величине меньше тех, что использованы в паттерне (ну скажем меньших 59) не имеется. Вроде как гарантия есть?

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

Тут мне надо от вас, Yadryara и Dmitriy40, новые "эталонные" n0, m, шаг и "паттерн", для примера, с которыми такой казус недофакторизации возникает с заметной частотой.

-- 18.03.2026, 10:33 --

Да, кстати! Напомнилась тут пренеприятная штука.
Процессоры в мобильных устройствах (телефоны, планшеты, ноутбуки) -- замедляются по перегреву.
Замедление из-за троттлинга может быть на от 10 до 30..40 процентов уже через минуту.
Поэтому тестовые запуски на скорость с хорошей повторяемостью можно делать если время работы меньше минуты. У меня на планшете (pari в одном потоке) скорость падает с 68 тыс цепочек в сек до 41 тыс к концу 2-й минуты.

Стационарных компов с нормальными кулерами это конечно не так касается, но мне нужны "короткие" забеги.

[Yadryara]

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

Участок кода, отсюда post1711836.html#p1711836 вот этот:

Это 4-я фильтрация. Она и сейчас есть в рабочей программе, только добавлено ещё формирование вектора оставшихся мест, и счётчик успеха в конце, а не в середине стоит.

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

Можно было бы надеяться, что если мы не будем проверять остаток(частное) на простоту, а продолжим поиск по таблице простых, то вскоре произойдёт перебор по таким найденным множителям. Но нет, оказывается, что если перебор в дальнейшем и происходит, то по времени сильно позже, чем если сделать проверку на простоту.

Это уже проверяли. Ведь 20-я степень двойки не от балды стоит. Она около оптимума была.

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

Соответственно, если число в цепочке разделилось на простое, то проверить не разделится ли ещё, и при том возможно, несколько раз, на то же простое

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

Есть опасение, что такая доп. проверка жутко съест время, но проверить-то надо.

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

Ещё я пока не понял, есть ли всё-таки гарантия, что простых множителей по величине меньше тех, что использованы в паттерне (ну скажем меньших 59) не имеется. Вроде как гарантия есть?

Да. В моём нынешнем поиске — простые в разных степенях от 2 до 73 включительно полностью расставлены. Поэтому 4-я фильтрация начинается с 79.

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

Тут мне надо от вас, Yadryara и Dmitriy40, новые "эталонные" n0, m, шаг и "паттерн", для примера, с которыми такой казус недофакторизации возникает с заметной частотой.

Так и знал, что только n0 вам не хватит Но у меня m это и есть шаг.

Подумаю. Эти три параметра-то (n0, m и v[]) у меня конечно есть, только светить не очень охота.

-- 18.03.2026, 11:37 --

Выслал три наборчика.

[wrest]

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

Подумаю. Эти три параметра-то (n0, m и v[]) у меня конечно есть, только светить не очень охота.

-- 18.03.2026, 11:37 --

Выслал три наборчика.

А вы подумайте ещё раз и засветите что не жалко засветить

Предыдущий набор, кстати, "эталонный" (отсюда post1711535.html#p1711535 ) был хорош ещё тем, что там была одна полная цепочка.

-- 18.03.2026, 11:53 --

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

Есть опасение, что такая доп. проверка жутко съест время, но проверить-то надо.

Вот я сейчас проверяю (на комплекте Dmitriy40 со траницы 24). Квадратов и кубов много (пока не считал). Но есть и биквадраты, 4..8 шт. на миллион цепочек.

[Yadryara]

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

Предыдущий набор, кстати, "эталонный" (отсюда post1711535.html#p1711535 ) был хорош ещё тем, что там была одна полная цепочка.

А откуда она взялась, эта полная цепочка? Потому что кое-кто её нашёл и объявил об этом 21-го октября. Тогда это был абсолютный мировой рекорд.

А по D(96, 20) конечно нет полной цепочки. Вроде никому в мире она не известна.

Если нужен ныне не актуальный набор чисел, но близкий, тогда есть варианты. Например, D(96, 19) со 2-го марта известна, вы, кстати, её прокомментировали. Паттерн можно прямо из неё вытащить.

[Dmitriy40]

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

Таким образом, на каждую цепочку делаем не менее одной проверки на простоту. Предположительно, именно эта проверка и является основным потребителем времени.

Это несложно проверить: замените ispseudoprime на 1 (условие срабатывает всегда) и замерьте время. Оно будет чуть заниженным, но если в среднем одна ispseudoprime на цепочку, то не сильно. И сравните насколько тормозит проверка простоты вместе с делением в аргументе.

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

Участок кода, отсюда post1711836.html#p1711836 вот этот:

Смотрите, тут выполняется одно короткое деление при получении d (пока k<2^43 для pr около 2^20, т.е. <8трлн цепочек, а раз до 2^20 доходит редко, то и для ещё больших k) для каждой цепочки и для каждого простого 59..2^20 (пока не оборвётся), потом выполняется в общем почти всегда короткое умножение (переполнения nn[] сверх 2^64 нечасты) и потом длинное деление только вместе с ispseudoprime, которое уже можно смело не считать (проверка простоты на два порядка медленнее деления).
В итоге самое долгое кроме ispseudoprime - %pr[i] при вычислении d, остальное (включая и умножение там же) слёзы.

Ещё, раз код именно такой, то в нём оказывается нет "терапевтики" т.е. отброса цепочек в которых простые 3..53 попали внутрь цепочки и увеличили степень. Обычно это делается примерно так: после получения правильного длинного n выполняем x=n+#v-1; if(x%3^6<#v, next); forprime(p=5,53, if(x%p^3<#v, next(2)); ); - всё, это отбросит цепочку если внутрь попали простые 3..53 (те что расставлены в паттерн, в данном случае в паттерне есть 3^5, остальные только в квадратах) и повысили свою степень (на чужие места они попасть не могут, только к себе же). Не знаю почему в Вашем коде этого нет, это прилично фильтрует неподходящие цепочки, ну или я не заметил.

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

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

Этим кажется Антон и занимается. Только смысла в этом немного: тесты показывали что степени выше первой встречаются где-то 1 на 10000 (отфильтровывались 10 цепочек из 191 из общего набора 100000), при том что квадрат вместо первой степени недопустим, только ещё высшие степени, которые ещё реже. Т.е. даже проверка на квадрат улучшит фильтрацию очень и очень незначительно, зато потребует (длинных) делений для каждого найденного делителя. Так что тут выбор, или вероятность пропустить решение (если появится куб в разложении, это миллионные доли вероятности) или вероятность не отбросить цепочку и продолжить её проверку (если степень выше первой и не подходит, это сотые процента) - или же продолжить проверку дальше, зато быстрее. Мы дружно посчитали что такие малые вероятности не стоят замедления перебора. Такую проверку можно добавить где-то на 5-7 этапе (не знаю на каком, не помню их смысл, конкретно перед сложной факторизацией), когда цепочек уже мало и сделать ещё раз factor(n,2^20) уже не сильно тормозит проверку, но никак не на 1-3 этапе, где цепочек ещё слишком много.

-- 18.03.2026, 15:04 --

Проверка какая степень у простого p в числе n+d-1: pows=valuation(n+d-1,p), даже без ручного цикла.

[wrest]

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

Проверка какая степень у простого p в числе n+d-1: pows=valuation(n+d-1,p), даже без ручного цикла.

О, это супер!

-- 18.03.2026, 15:35 --

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

Ещё, раз код именно такой, то в нём оказывается нет "терапевтики" т.е. отброса цепочек в которых простые 3..53 попали внутрь цепочки и увеличили степень.

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

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

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

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

Так вот, через фильтр "недостаточных" чисел просачивается меньше одной цепочки на миллион.
Например такие:

(Оффтоп)

? n+10
%16 = 1171268497219384836289125617080939951768409613979
? factor(n+10)
time = 94 ms.
%17 =
[ 47 2]

[ 22083066567468453139 1]

[24010508904831364007001529 1]

? n+11
%18 = 1171268497219384836289125617080939951768409613980
? factor(n+11)
time = 219 ms.
%19 =
[ 2 2]

[ 5 1]

[ 25114053327637 1]

[2331898562806767684695709487568527 1]

?

И вот например в "эталонном" пакете, до цепочки D(48,21) нет ни одной которая бы просочилась.