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

[wrest]

Пока суть да дело, написал детектор паттернов
Он пытается определить паттерн (хотя я точного терминна не знаю, может и не паттерн) по по числу
Код:

Используется синтаксис C++

pat(base,chain_len,prime_lim,mode=0)={
  \\ Детектор паттерна, т.е. какие простые множители, меньшие lim входят
  \\ в разложение чисел вида n=base+d где d=0..len-1
  \\ возвращает вектор длиной len состоящий из "постоянных" делителей паттерна
  \\ вычисляем вектор делителей
    my(v=vector(chain_len,i,1));
    forprime(p=2,prime_lim,
      for(d=0,chain_len-1,
        my(bd=base+d); \\ анализируемое число в цепочке на позиции d, старт с d=0
        while(bd%p==0,
          v[d+1]*=p;bd=bd/p; 
        );
      );
    );

  if(mode==1, \\ возвращаем результат в виде "стандартных" факторизаций
    v=vector(chain_len,d,factor(v[d]));
  );
    
  if(mode==2, \\ возвращаем результат в виде вектора [[p1,a1],[p2,a2]],[[p1,a1],[p2,a2],[p3,a3]],...]
    v=vector(chain_len,d,Vec(Col(factor(v[d]))));
    );
  
  if(mode==3, \\ возвращаем результат в виде вектора с множителями для количества делителей
     v=vector(chain_len,d,numdiv(v[d]));
    );
  return(v);
}

Число n0 из которого будет извлекаться паттерн, берём отсюда:

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

v=[63, 3610, 3179, 12, 17797, 3362, 75, 392, 841, 18, 2209, 20, 1587, 242, 6727, 96, 14045, 338, 243, 68, 35131];
n0=283938699868309713921641266159023371777169;
m=229403502054304075118105309394590566946400;
nu=[3, 2, 3, 3, 3, 3, 3, 2, 4, 3, 4, 3, 3, 3, 3, 2, 3, 3, 3, 3, 3];

Запуск:

1. ? \r pat_detect.gp 
2. time = 1 ms. 
3. ? n0=283938699868309713921641266159023371777169; 
4. ? pat(n0,21,59) 
5. time = 1 ms. 
6. %4 = [63, 3610, 3179, 12, 17797, 3362, 75, 23128, 841, 18, 2209, 20, 1587, 242, 6727, 96, 14045, 338, 729, 68, 35131] 
7. ? pat(n0,21,59,1) 
8. time = 1 ms. 
9. %5 = [[3, 2; 7, 1], [2, 1; 5, 1; 19, 2], [11, 1; 17, 2], [2, 2; 3, 1], [13, 1; 37, 2], [2, 1; 41, 2], [3, 1; 5, 2], [2, 3; 7, 2; 59, 1], Mat([29, 2]), [2, 1; 3, 2], Mat([47, 2]), [2, 2; 5, 1], [3, 1; 23, 2], [2, 1; 11, 2], [7, 1; 31, 2], [2, 5; 3, 1], [5, 1; 53, 2], [2, 1; 13, 2], Mat([3, 6]), [2, 2; 17, 1], [19, 1; 43, 2]] 
10. ? pat(n0,21,59,2) 
11. time = 3 ms. 
12. %6 = [[[3, 2], [7, 1]], [[2, 1], [5, 1], [19, 2]], [[11, 1], [17, 2]], [[2, 2], [3, 1]], [[13, 1], [37, 2]], [[2, 1], [41, 2]], [[3, 1], [5, 2]], [[2, 3], [7, 2], [59, 1]], [[29, 2]], [[2, 1], [3, 2]], [[47, 2]], [[2, 2], [5, 1]], [[3, 1], [23, 2]], [[2, 1], [11, 2]], [[7, 1], [31, 2]], [[2, 5], [3, 1]], [[5, 1], [53, 2]], [[2, 1], [13, 2]], [[3, 6]], [[2, 2], [17, 1]], [[19, 1], [43, 2]]] 
13. ? pat(n0,21,59,3) 
14. time = 3 ms. 
15. %7 = [6, 12, 6, 6, 6, 6, 6, 24, 3, 6, 3, 6, 6, 6, 6, 12, 6, 6, 7, 6, 6] 
16. ? 

Это чтобы в функцию которая цепочки фильтрует (в моём авторстве называется em3(),  на 29 странице темы post1711836.html#p1711836 ), не передавать параметры, можно передать только n0
На всякий случай написал так что возвращаться может в разных форматах.

Но есть и проблемы, похоже.
Например, у числа n0+17 предполагается "встроенный множитель" $243=3^5$ а в реальности там есть $729=3^6$

Говорилось где-то в теме, что проверять надо на наличие простых множителей начиная с 59, а тут выходит, что в числе n0+17 имеем (после деления на 3^5) простой делитель 3.

[Yadryara]

wrest

Ой какой вы молодец, что пытаетесь вникнуть!

Ну вроде понял. Я вам скажу только n0, и вы только лишь по нему определите сколько делителей на каких местах уже собрано??

Ну для последнего счёта, это известно, вам есть на что ориентироваться: на десяти местах уже есть по 12 делителей и ещё на десяти по 6 делителей.

Я вам скажу какое-нибудь своё n0, а вы мне скажете на каких именно местах и покажете паттерн v ?

Вот не знаю, стоит ли это публично показывать.

-- 17.03.2026, 14:31 --

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

Например, у числа n0+17 предполагается "встроенный множитель" $243=3^5$ а в реальности там есть $729=3^6$

Говорилось где-то в теме, что проверять надо на наличие простых множителей начиная с 59, а тут выходит, что в числе n0+17 имеем (после деления на 3^5) простой делитель 3.

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

[wrest]

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

Ой какой вы молодец, что пытаетесь вникнуть!

Я дую в свою дуду: для быстроты и удобства нужна универсальная функция, максимально оптимизированная, готовая к параллельной работе, и которая хорошо делаёт своё дело: фильтрует порядка миллиона цепочек за присест. При этом, функции должно быть всё равно, что вы ищете: D(48,24), D(96,20) и т.п. Универсальность должна быть в унифцированном наборе и типе параметров (api) которые передаются в функцию.
Упоминаемая em3() с 29-й страницы почти такая, за исключением нескольких строк где описан пртверяемый "паттерн", ч5го там быть не должно. Опубликованная выше функция pat() старкется через минимальное количество параметров создать структуру "паттерна", и работает ~1..3мс что мизер по сравнению с фильтрацией миллиона цепочек.

[Yadryara]

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

для быстроты и удобства нужна универсальная функция,

Удобства скорее всего несомненные, а вот быстрота и результативность под большим вопросом.

Уточнил схему. У вас возник вопрос где-то в районе её 2-го пункта.

Это нынешняя схема для 96 делителей, для серии без простых:

1-я фильтрация вне цикла по i: генерация паттерна v и вычисление lcm по нему.
2-я фильтрация вне цикла по i: терапевтика по 2 и 3.

Вычисление шага m и остатка по нему — n0.

Внутри цикла по i:

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

Если серия с простыми, то между 3-й и 4-й фильтрациями добавляются ещё две. Так что пока не будем об этом.

[wrest]

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

Удобства скорее всего несомненные, а вот быстрота и результативность под большим вопросом.

Тут как вам будет угодно. Мы же свободные люди

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

Так что пока не будем об этом.

Ну, вы о своём, а я о своём. Плюрализм.

-- 17.03.2026, 15:37 --

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

1-я фильтрация вне цикла по i: генерация паттерна v и вычисление lcm по нему.
2-я фильтрация вне цикла по i: терапевтика по 2 и 3.

Вычисление шага m и остатка по нему — n0.

Вот и вынесите это в отдельную функцию, которая рожает n0, m и что-нибудь ещё. Зафиксируйте интерфейс (что рожается) и сдавайте результат в следующую(-е) функцию.

[Dmitriy40]

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

Но есть и проблемы, похоже.
Например, у числа n0+17 предполагается "встроенный множитель" $243=3^5$ а в реальности там есть $729=3^6$

Там дальше в цикле проверяются числа n0+m*2, n0+m*4, n0+m*6 и так далее с шагом m*2, так вот, первое и второе число уже делится лишь на 3^5, зато третье аж на 3^9. Такие неподходящие числа отсекаются проверками уже в самом цикле, в паттерне так получилось что в n0 попала 6-я степень. Можно конечно продвинуть n0 до n0+m*2, но я хотел чтобы n0 было меньше m, как и должен быть остаток по модулю.

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

Но Дмитрий, похоже, этого не понимает.

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


И насчёт Полларда и ECM.
Вот интересное сравнение скорости разложения:

? isnull(Z_pollardbrent(2^257-1,10000,2))
time = 267 ms.
%1 = 0
? isnull(Z_pollardbrent(2^257-1,100000,2))
time = 2,575 ms.
%2 = 0
? isnull(Z_pollardbrent(2^257-1,1000000,2))
time = 19,640 ms.
%3 = [535006138814359, 432862656469423142931042426214547535783388063929571229938474969]
? pollardRho_limited(2^257-1,1,1000000)
time = 5,054 ms.
%4 = [0, 0, 0, 0]
? pollardRho_limited(2^257-1,10,1000000)
time = 50,295 ms.
%5 = [0, 0, 0, 0]
? pollardRho_limited(2^257-1,1,10000000)
time = 50,170 ms.
%6 = [0, 0, 0, 0]
? isnull(Z_ECM(2^257-1,1000,2,11000))
time = 1,904 ms.
%7 = 535006138814359

Теперь то понятно почему я агитирую за ECM вместо Полларда?
Заметьте, используемая реализация Полларда, хотя и работает быстрее, но вообще не нашла делитель, даже за значительно большее количество проверок.

[Yadryara]

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

для быстроты и удобства нужна универсальная функция

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

Только считала она в триллион раз медленнее. Серьёзно. В триллион.

Так что если ваша в будет в миллиард раз медленнее, расстраиваться не надо

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

Теперь то понятно почему я агитирую за ECM вместо Полларда?

Пока нет, но спасибо, изучу. У меня же нет предвзятого отношения. Там где будет ЕСМ лучше, нужно будет её использовать.

Никто вроде не торопит, можно попробовать так/сяк/наперекосяк

[wrest]

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

Можно конечно продвинуть n0 до n0+m*2, но я хотел чтобы n0 было меньше m, как и должен быть остаток по модулю.

Я первоначально думал передавать в функцию n0 и m, и взять 10 первых цепочек и по каждому порядковому номеру в цепочке выбрать минимальный делитель, состоящий из простых меньших некоторого (59). Но не был уверен что это правильный подход - ведь если случается увеличение с степени, то может случиться и уменьшение? Или не может?

Ну и это так, просто ирструмент проверки. Возможно, "паттерн" надо передавать в функцию как-то более явно а не в виде n0 и m

[Dmitriy40]

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

ведь если случается увеличение с степени, то может случиться и уменьшение? Или не может?

Относительно паттерна - не может. Относительно n0 - Вы только что обнаружили что может.

[wrest]

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

Вот интересное сравнение скорости разложения:

Вы поробуйте с ключом \g 4 понаблюдать как работает встроенный фактор. Захватывающее зрелище:
default(debug,4);print(factor(2^257-1));default(debug,0)
Он полларда прерывает по какому-то порогу.
Для ECM при правильных параметрах у встртенного factor получается быстрее, чем при ваших параметрах:

ECM: working on 48 curves at a time; initializing for up to 16 rounds...
ECM: time =      0 ms
ECM: B1 = 1800, B2 = 198000,    gss =  128*420
ECM: time =    267 ms, B1 phase done, p = 1801, setting up for B2
ECM: time =      5 ms, entering B2 phase, p = 2017
ECM: time =     49 ms
found factor = 535006138814359

Поробуйте например

isnull(Z_ECM(2^257-1,16,1,470))

[Yadryara]

D

[Dmitriy40]

Да, подбором параметров можно ускорить, например isnull(Z_ECM(2^257-1,5,1,500)), но такой подбор - уже не универсально.

[wrest]

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

Да, подбором параметров можно ускорить, например isnull(Z_ECM(2^257-1,5,1,500)), но такой подбор - уже не универсально.

Так встроенный factor как-то же подбирает... Людиидумали, эксперементировали, в муках вывели универсальные параметры.
Я так понимаю, выбор B1 это какая-то функция от логарифма (битности) числа. Надо опять ковыряться...
Ну и -- мы ведь по-прежнему не рассчитываем что крякнутся все числа, нам надо чтобы заметное большинство, но быстро. А остальных крякнем на 8-й фильтрации. Тут главное, чтобы по возможности не повторять те вычисления, которые уже произведены и не дали результата.
Вот и надо как-то определить, что например полларду даём 100мс (а это столько-то итераций, либо прерываем таймером), ECM-у даём 400мс (такие-то начальные параметры или прерываем таймером), а если не вышло, выкатываем базуку встроенный factor, отключаем ему полларда и первую стадию ECM и уж там как получится.

[Dmitriy40]

Yadryara
Интересно, а Вы понимаете что сравнение d==n в Полларде никогда не выполняется? И значит его проверка лишняя. Как и проверка d<n чуть выше (истинна всегда).

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

Я так понимаю, выбор B1 это какая-то функция от логарифма (битности) числа.

Точнее от желаемой битности делителя, примерно. А так как ECM запускается примерно до кубического корня из самого числа (для малых чисел может и дальше, не знаю, но для полупростых чисел больше скажем 1e40 MPQS должен быть уже быстрее ECM), то и от величины числа B1 выходит что зависит. Но тут много дополнительных предположений и оптимизаций.

А Поллард запускается перед ECM потому что видимо он существенно проще и быстрее ECM (в смысле каждая отдельная итерация быстрее) на малых числах или малых делителях. Но для больших чисел и отсутствия совсем малых делителей Поллард дольше и хуже ECM, во всяком случае при факторизации YAFU нескольких тысяч 60+ значных чисел (с 2-4 простыми делителями не менее 10 знаков) я кажется ни разу не видел чтобы Поллард что-то нашёл, а ECM находил относительно часто.

-- 17.03.2026, 17:43 --

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

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

Мне думается при столь небольших числах (порядка 60 знаков) оптимизировать последнюю фильтрацию не имеет смысла, пусть проверяет хоть всё заново, это по любому доли процента времени проверки и специально экономить их - извращение переоптимизация.
Смотрите, Антон говорил что до последней фильтрации вроде бы доходят 11 чисел в час, при этом проверка одной цепочки занимает в среднем 20с (самым тупым numdiv), что всего 6%. А если проверять только недоразложенные места, то единицы секунд и процент-два общего времени. Ну и зачем её оптимизировать? Лучше оптимизировать предыдущие проверки, чтобы чисел вываливалось меньше при том же темпе проверок.

[Yadryara]

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

Yadryara
Интересно, а Вы понимаете что сравнение d==n в Полларде никогда не выполняется? И значит его проверка лишняя. Как и проверка d<n чуть выше (истинна всегда).

Нет, не понимаю. Иначе я бы давно убрал лишние проверки.

Просто ещё не смотрел внимательно это место кода.