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

[wrest]

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

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

Ну вот к моему удивлению, если и быстрее то незаметно.

Но с точки зрения чтения текста, менее понятно. Так что я у себя вернул код типа
if(n%3^7>len && n%3^6<len , next);- тут n длинное и оно вычисляется до того
а с индексом цикла k у меня получался такой
if(k%3==0 && k%9!=3, next()); - тут всё короткое и n не вычисляется до этого оператора

-- 26.03.2026, 18:46 --

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

А вот для неразмещённых простых придётся остаток проверять по списку, а не просто <len, и как из него быстро получить правильный d для каждого простого не очень понятно.

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

-- 26.03.2026, 19:05 --

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

Если бы Вы посмотрели на любой код VAL, то там так и сделано.

Ну так он эту тему 10 лет копает уже :)
Я же всё-таки хочу как-то более универсально написать, чем сейчас.
В em4() с 63 страницы я например вычисляю максимальное встроенное простое из паттерна, а не задаю хардкодом:

my(pat_prime_lim:small=nextprime(vecmax(factor(vecprod(v))[,1])+1));

Например, "терапевтика". С ней надо бы подразобраться. Например: а почему она такая и какая будет для других паттернов? Ну по тройкам она такая потому, что в одно из чисел цепочки встроено простое 3^5, и через два на третий там будет появляться 3^6, а поскольку 48 не делится на 6+1=7, можно откниуть практически треть цепочек "не глядя". Но если поглядеть, то из этой трети надо вернуть в оборот тоже треть которая будет давать допустимое 3^7 т.к. 48 делится на 7+1=8, и таким образом откинуть надо не 3/9, а 2/9. И это должно стать понятно программе, чтобы программно определить параметры "терапевтики".

Почему кубы встроенных простых выкидываем на втором шаге терапевтики?
Ну потому что куб даёт 3+1=4 делителя и из этого делается пока для меня загадочный вывод, что для успеха такого числа в нём должен засесть квадрат ещё одного простого, который даст 2+1=3 делителя, а вместе они дадут 3*4=12 делителей. Вот из структуры паттерна программа, зная что дальше начальные числа будут считаться как n=n0+k*m, должна бы вычислить, что именно надо подвергнуть "терапевтике".
Все предварительные вычисления, включая таблицу простых например до 2^24 это меньше секунды.

[Dmitriy40]

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

и из этого делается пока для меня загадочный вывод

Задача не стояла найти все цепочки, задача стояла найти любую цепочку - и это позволяет пропускать сильно менее вероятные комбинации в пользу простоты кода и скорости перебора.
А вероятность обнаружить в разложении куб простого плюс ещё и квадрат простого вместо нескольких простых в первой степени (а квадрат первого простого мы уже и так сунули) существенно ниже, на порядки. И потому игнорируется.
Как и возможность получить 3^7, её проверка добавит лишь 1/9=11% цепочек в проверку, зато потребует лишнего деления (вычисления остатка). Плюс к ней ведь ещё понадобится простое в квадрате, что слишком маловероятно.
Помнится некоторое время назад собирали статистику вероятностей степеней, правда среди всех нечётных чисел.

[wrest]

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

Как и возможность получить 3^7, её проверка добавит лишь 1/9=11% цепочек в проверку, зато потребует лишнего деления (вычисления остатка).

Одно лишнее деление на цепочку это мелкие расходы. Лишний ispseudoprime -- средние, лишний numdiv - крупные.

-- 26.03.2026, 21:16 --

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

её проверка добавит лишь 1/9=11% цепочек в проверку,

Да, увеличивает нагрузку на табличную проверку с 27% до 38% от общего количества цепочек.

[Dmitriy40]

wrest
Не просто одно лишнее деление на цепочку, а лишнее деление на 11% цепочек ради выигрыша тысячных процента цепочек (и 3^7 и ещё p^2). ИМХО скорость перебора +10% важнее обнаружения на 0.01% больше подходящих цепочек.

[wrest]

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

ИМХО скорость перебора +10% важнее обнаружения на 0.01% больше подходящих цепочек.

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

Посчитал. Ну всё банально и ровно. Первое число - количество делителей в паттерне, второе - относительная частота отсева этого места. Больше делителей в паттерне - чаще отсев
3;12
6;100
12;760

[DemISdx]

К сведению.

(Оффтоп)

Yadryara сообщил, по другим каналам связи, что у него форум перестал открываться.
От слова совсем.
Остальные сайты вроде работают, по крайней мере частично.