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

[Yadryara]

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

Нормальная работа отлаженной программы - ничего не находить. Поэтому трудно понять:, не находит потому что пропускает или потому что работает правильно.

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

[Dmitriy40]

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

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

Ослабляйте условия отсева и внимательно проверяйте что вываливается, правомочно ли оно отсеялось нормальными условиями или нет. На скорость внимания не обращать.

(Анекдотичный случай)

У меня вот тут по другой задаче после долгого счёта на асме вдруг насчиталась сумма цифр числа 9999999995^4 аж 290 вместо правильной 175 ... При том что меньшие числа посчитались вроде правильно. Хорошо число слишком подозрительное и перепроверил, а так бы и пропустил.
Оказалось алгоритм Баррета ошибается с частным, его приходится восстанавливать если остаток больше делителя.

[wrest]

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

Считаю отброшенные цепочки разными счётчиками (везде перед next(2) ставлю счётчик), но в сумме получается, что отброшено цепочек немного больше чем вошло в анализ

Пересчитал формулой прям в программе, теперь норм. сходится.
Я просто забеспокоился насчёт next-ов, что оно считает "циклами".

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

Тут я думаю, что надо вернуться к идее default(factor_add_primes,1), чтобы не возиться с вышеописанным, а просто сделать поллардов сколько получится и сдать на проверку numdiv-у, который подберёт найденные поллардом простые и мгновенно дофакторизует.

То что я написал покашта -- не помогает почему-то, возможно из-за того, что я запутался в логике.
У меня на полларда попадает только найденная D(48,21), ни до ни после (в пределах 10 млн.) на полларда не попадает ни одна... Подозреваю какой-то косяк.

-- 19.03.2026, 18:16 --

Похоже, с размером таблицы имеет смысл поиграть в пределах 2^20..2^24

[maxal]

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

if( default(primelimit)<2^24, default(primelimit,2^24) );
default(factor_add_primes,1);

{ timefact(N,sec)=
    iferr(
      alarm(sec);
      factor(N);
      ,E,
    );
    alarm();
    factor(N,0);
}

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

[wrest]

maxal в сообщении #1720675 писал(а):

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

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

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

[Dmitriy40]

maxal

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

Второе, alarm+factor глючит! Когда я писал факторизацию чисел 70+ знаков то на это наткнулся и писал об этом в теме про PARI (и ещё штук 7 сообщений далее). Причём aitap там дальше увидел что ошибка в исходнике (плохая синхронизация потоков с таймером).

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

Factor() ни при чём, валится alarm(), при дальнейшем разбирательстве в теме про PARI даже нашли в каком месте исходника вероятна ошибка.

Так что доверять alarm, по крайней мере под виндой, стоит с оглядкой.

-- 19.03.2026, 23:25 --

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

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

По найденному делителю останавливаются и Поллард и ECM, это не проблема. Другое дело что делитель не всегда простой, но это уже другой вопрос, тоже несложный (результат f[] от встроенного Полларда можно дофакторизовать командой factor(vecprod(f[1..-2])), т.е. без последнего числа-частного, это по идее очень быстро, делитель же обычно невелик).
А для ограничения времени у обоих алгоритмов есть количество итераций, можно их ограничивать.

Yadryara, wrest
Кстати, если/когда будут повторные запуски Полларда или ECM для тех же мест цепочки, стоит указывать другой seed (его вообще часто берут случайным), это должно повысить вероятность нахождения делителей.

[wrest]

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

По найденному делителю останавливаются и Поллард и ECM, это не проблема.

Тут проблема в правильном подборе параметров для этих методов. Надо погрузитьсяв код и разобрать

-- 20.03.2026, 00:26 --

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

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

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

[Dmitriy40]

wrest
Время одной итерации Полларда зависит от величины чисел.
Время одной итерации ECM зависит и от величины чисел, и от выбранного B1 (величины ожидаемого делителя). Про выбор B1 цитировал например тут: post1701712.html#p1701712 (D там это искомый делитель).
Ну и зачем выдумывать что-то совсем универсальное ... Проще по месту подбирать желаемые значения для каждого случая снова.

[wrest]

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

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

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

А встроенная факторизация почему-то чередует методы.

Кстати, я тут опять читал мануал и наткнулся на forfactored(N = a, b, seq)
https://pari.math.u-bordeaux.fr/dochtml ... orfactored
но не понял как оно работает.
upd понял как работает, нам не надо

[Yadryara]

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

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

Ну вот дошли руки посмотреть внимательно.

Сильно большие числа не смотрел, но вот, например, составные n, для которых d ==n, наоборот, как раз выполняется (при лимите в 30 тысяч итераций):

n = 10000005101   iter = 450        [60901, 1; 164201, 1]
n = 10000008569   iter = 234        [82903, 1; 120623, 1]

[wrest]

Yadryara
На заметку. Вот так во встроенной факторизации вычисляют "оптимальное" количество итераций полларда
Код на Си:

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

  size = expi(n) + 1;
  /* nonlinear increase in effort, kicking in around 80 bits */
  if (size <= 301) /* 301 gives 48121 + tune */
    c0 = tune + size-60 + ((size-73)>>1)*((size-70)>>3)*((size-56)>>4);
  else
    c0 = 49152; /* ECM is faster when it'd take longer */

перевод на pari:

{
iter(n:int)=
my(
size:small=logint(n,2)+1,
tune:small=14,
c0:small = if(size>301,
                       49152
                      ,
                       tune + size-60 + ((size-73)>>1)*((size-70)>>3)*((size-56)>>4)
              )
  );
return(c0);
}

Есть комментарий в тексте:
const long tune = 14; /* FIXME: retune this */
Запуск:

forstep(n=20,120,5,print("10^",n," ",iter(10^n)," iterations"))
10^20 21 iterations
10^25 43 iterations
10^30 132 iterations
10^35 401 iterations
10^40 927 iterations
10^45 2004 iterations
10^50 3505 iterations
10^55 5527 iterations
10^60 9226 iterations
10^65 12950 iterations
10^70 17787 iterations
10^75 23436 iterations
10^80 30172 iterations
10^85 38457 iterations
10^90 47713 iterations
10^95 49152 iterations
10^100 49152 iterations
10^105 49152 iterations
10^110 49152 iterations
10^115 49152 iterations
10^120 49152 iterations
?time = 1 ms.
?

Если число длинее 301 бит, то iterations=49152

[Dmitriy40]

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

вот, например, составные n, для которых d ==n, наоборот, как раз выполняется (при лимите в 30 тысяч итераций):

Мда, забыл что gcd(0,n)=n.
Тогда вместо d==n логичнее проверять x==y перед gcd.

[wrest]

Дописал вроде новую версию em3() c 29 страницы.
С поллардом и mpqs-ом, и честным подсчётом высших степеней табличных простых.
Из ~20 миллионов цепочек до фирального numdiv-а прошла одна, которая и прошла.
С терапевтикой в однопотке на планшете скорость ~190 тыс/сек, без - ~60 тыс./сек
То есть скорость в итоге повысилась за счёт терапевтики, а вот поллард дополнительно скорость не повышает.
Но я наткнулся на необходимость ещё одной проверки: по тем числам где делителей мало, я проверяю остаток(частное) на простоту, и выявляю числа с явным недобором (только проверка остатка(частного) на простоту), их оказывается примерно 55 цепочек на миллион в случае терапевтики и 170 если без. На стадии табличной проверки это наверное было бы замедлением, а вот после - норм. И уже после этой проверки, когда отсеяны цепочки с явным недобором, наступает черёд полларда, и если он не смог, то mpqs-а.

Статистика.
Без терапевтики, 20 млн цепочек:

Поиск D(48,21)
База n0=283938699868309713921641266159023371777169
шаг 2*m=458807004108608150236210618789181133892800
Задание: Старт: 0 шагов:20000000 Таблица простых до:1048576
Паттерн:секретный. Подготовился за:25 ms
Дошло до numdiv:52556626259340931919271848023566857910792017169
Найдено D(48,21):52556626259340931919271848023566857910792017169
666-й поток кончил. Дошло до numdiv: 1 Найдено:1 Отброшено:19999999
Фильтры терапевтика:0 таблица:19996537 недобор:3430 Поллард/mpqs:32  numdiv:0
Проверок псевдопростых:21024595 Проверок поллардом/mpqs начато:101 Поллард/mpqs нашёл множитель:111

С терапевтикой, те же 20 млн.

Поиск D(48,21)
База n0=283938699868309713921641266159023371777169 
шаг 2*m=458807004108608150236210618789181133892800 
Задание: Старт: 0 шагов:20000000 Таблица простых до:1048576 
Паттерн:секретный. Подготовился за:13 ms  
Дошло до numdiv:52556626259340931919271848023566857910792017169
Найдено D(48,21):52556626259340931919271848023566857910792017169  
666-й поток кончил. Дошло до numdiv: 1 Найдено:1 Отброшено:19999999  
Фильтры терапевтика:14556473 таблица:5442409 недобор:1109 Поллард/mpqs:8  numdiv:0  
Проверок псевдопростых:5760033 Проверок поллардом/mpqs начато:47 Поллард/mpqs нашёл множитель:52

Поллард/mpqs находит больле множителей чем начато проверок потому, что в ходе одной проверки, если остаток(частное) композитный, он запускается на проверку поллардом/mpqs опять.

Код для проверки mpqs-ом

install(mpqs,G);
my_mpqs(n:int)=my(divisor=component(mpqs(n),1));return([divisor,n/divisor]);

возвращает два множителя. Их надо, по-хорошему, оба проверять на простоту.

Вероятность там поймать составное уже совсем небольшая, но эта логика у меня недописана пока.

В итоге, я думаю отказаться от полларда в пользу mpqs-а, а то и factorint-а.

[Dmitriy40]

wrest
А если Полларда и MPQS заменить на ECM с примерно тем же временем работы для случая ненахождения делителя?

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

В итоге, я думаю отказаться от полларда в пользу mpqs-а, а то и factorint-а.

А разве mpqs можно ограничить по времени работы (кроме как alarm)? Она же по идее работает до упора, до нахождения делителя.
Плюс она же память жрёт весьма активно, в отличие от Полларда и ECM.

А можно узнать сколько вызовов ispseudoprime было ради отброса 1109 цепочек с недобором делителей? Если что счётчик q можно увеличивать так: if( ... && q++ && ispseudoprime(...), ...). Или это количество равно 5760033-5442409=317624?
Может имеет смысл отказаться от такой проверки и пропустить 1109 цепочек на следующую проверку (Поллард/MPQS/ECM/factor)?

И ещё вопрос, а сколько времени займёт numdiv (от недоразложенных мест) для 8 цепочек дошедших до Полларда/mpqs если их отменить? Не выйдет ли так быстрее, без Полларда/mpqs вообще?

[wrest]

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

А если Полларда и MPQS заменить на ECM с примерно тем же временем работы для случая ненахождения делителя?

Тут два пока два препятствия:
1. Надо собрать то, что попадает на полларда сейчас. Тестовый набор, так сказать, ну скажем из 100 чисел хотя бы.
2. Надо определить как правильно запускать ECM. Полларда я запускаю как во встроенной факторизации. MPQS без параметров - сам подбирает. А вот с ECM неясно).

-- 21.03.2026, 00:37 --

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

И ещё вопрос, а сколько времени займёт numdiv (от недоразложенных мест) для 8 цепочек дошедших до Полларда/mpqs если их отменить? Не выйдет ли так быстрее, без Полларда/mpqs вообще?

Вот именно об этом я и думаю. Кстати, numdiv можно запускать так: numdiv(factorint(n,flag))
Эти функции понимают возвращаемый факторизацией формат (матрицу). Это даёт возможность настроить factorint по флагу и не считать numdiv "руками".

-- 21.03.2026, 00:46 --

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

Может имеет смысл отказаться от такой проверки и пропустить 1109 цепочек на следующую проверку (Поллард/MPQS/ECM/factor)?

Не думаю. Там же всё таки только ispseudoprime и всё. Надо бы посчитать, конечно. Запустил счёт.
Но только теперь числа с недобором все будут проходить на numdiv, т.к. на стадии полларда проверяется перебор или окончание факторизации. Соответственно, недобор не проверяется

С замером времени засада на планшете. Очень нестабильно - чуть поработает и тротлит А может андроид там чегонибудь задумает и смещает с производительного ядра насоседнее и т.п. Никакого контроля/мониторинга ж нет, юзерские приложения не могут эти системные данные читать: нужен root.
Надо на ноуте тестить...