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

[wrest]

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

Ну вот я же неслучайно ещё и самую правую колонку расписал:

Осталось только оптимизировать полную факторизацию numdiv, заменив (если получится) на более быструю проверку на полупростоту. Но может и не получиться т.к. numdiv встроенная и уже максимально быстрая факторизация.

[Dmitriy40]

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

Почему в одном случае удивительно, а в другом — нет.

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

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

Ну вот ещё ускорить удалось, сделав цикл по тому простому которое с 3-кой:

Согласен, уменьшение количества итераций полезно практически всегда (когда не слишком усложняет внутренний код).

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

Ну в практическом смысле, например, поиск 21-к вроде актуален, причём сразу в нескольких смыслах.
[...]
Так что логично было пока что рассмотреть цепочку попроще.
На любых доступных языках, лишь бы быстрее было.

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

Искать КПППЧ21 на PARI - редкое извращение: при ожидаемом количестве вариантов за квинтиллион (1e18) попасть на решение можно лишь случайно. Соответственно обсуждать специфичные именно для PARI способы ускорения (например возведение -1 в степень вместо простого if) в плане применения их к поиску КПППЧ21 - не слишком разумно.

Если же речь про M48n21, то да, её на PARI искать можно (n20 же нашлась), но почему тогда не сказать об этом сразу и прямо, мол как ускорить поиск M48n21, а не просто "быстрые программы" не пойми на чём и для чего. И многие методы ускорения для M4n3 и M48n21 будут разными, потому что при их поиске тормозят разные команды. Например для чисел где-то до 1e60 factor() (и соответственно numdiv()) вполне справляется, а для сильно более длинных приходится его ограничивать левыми (и глючными!) средствами и оставлять кандидаты на внешнюю ручную проверку. Или проверять числа не подряд до упора (получения точного значения numdiv), а пытаясь максимально быстрыми тестами отбросить кандидата как можно раньше, чего для M4n3 просто не нужно. И так далее.

Потому я не вполне понимаю как можно обсуждать "всё в одном", и PARI, и С/асм, и короткие цепочки, и длинные.

-- 24.09.2025, 15:42 --

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

Осталось только оптимизировать полную факторизацию numdiv, заменив (если получится) на более быструю проверку на полупростоту. Но может и не получиться т.к. numdiv встроенная и уже максимально быстрая факторизация.

Не скажите, можно пробовать заменить numdiv() на быструю (да ещё и многопточную) внешнюю прогу, например ту же YAFU.
И опять же, есть большая разница в использовании YAFU для чисел до 1e50 (секунды на разложение) и свыше 1e120 (часы) или 1e200 (годы) и методы использования тоже будут разными. Для больших чисел даже ispseudoprime() тормозит и придётся её предварять какими-то ещё более быстрыми тестами.

-- 24.09.2025, 15:52 --

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

заменив (если получится) на более быструю проверку на полупростоту

Насколько я понимаю для чисел общего вида нет способа отличить разложение pq от pqr (на два или на большее количество простых).

-- 24.09.2025, 15:57 --

Кстати про M48n21. Ведь при их поиске можно вообще отказаться от факторизации и разместить по всем местам столько малых простых, чтобы неизвестными остались лишь ровно по одному простому в каждой позиции. Искомые числа резко возрастут, вероятность нахождения ещё резче снизится, зато ispseudoprime сильно быстрее numdiv/factor. И что пересилит ещё вопрос.
Как и вопрос искать ли по одному паттерну или сразу по всем. VAL же ищет по одному (или нескольким, не уверен, но точно не по сотням тысяч) и находит, в том числе мировые рекорды, значит и такой подход имеет право на жизнь и может быть выгоднее перебора всех возможных паттернов (как делалось для пентадекатлона M12n15 и некоторых других).

[Yadryara]

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

Если же речь про M48n21, то да, её на PARI искать можно (n20 же нашлась), но почему тогда не сказать об этом сразу и прямо,

Ну и опять останемся мы в теме от силы вдвоём — народ разбежится увидев насколько это сложно.

А так всё-таки и wrest и gris и mihaild подключились.

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

не пойми на чём и для чего.

Ну а я могу сказать что искать любую 21-ку — не пойми зачём это надо.

Насчёт не пойми на чём, Вы сами только что сказали, что CUDA и/или GPU может очень быстро считать. Вот именно что не пойми на чём надо считать и хотелось бы разобраться.

Так что пусть идёт как идёт. Вдруг активность ещё какое-то время сохранится.

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

возведение -1 в степень вместо простого if

Я вспомнил про него, но вроде он не совсем простой. Поленился разбираться как правильно этот иф записать.

[Yadryara]

waxtep конечно же ещё заглядывал. Вот, кстати и спрошу. Вы дважды пытались с кортежами позаниматься, но не очень сложилось. Задачи показалось слишком сложными? Хотя может и по другим причинам мог интерес пропасть.

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

wrest, вот я рад что вы пишете когда чего-то непонятно. Сейчас-то понятно? Скажу на всякий случай. Если для куаров остатки по модулю 12 именно 1 и 11, то для $2p$ они 2 и 10, не правда ли? А для $3p$ они 3 и 9.

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

[wrest]

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

Я вспомнил про него, но вроде он не совсем простой. Поленился разбираться как правильно этот иф записать.

Так: if(p%3==2,1,-1) но ускорения нет, я проверил.

-- 24.09.2025, 20:03 --

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

Насколько я понимаю для чисел общего вида нет способа отличить разложение pq от pqr (на два или на большее количество простых).

При факторизации просто останавливаться, когда найдено два фактора, типа если нашли два фактора, а число ещё не закончилось, то дальше уже не факторизовать.

[VAL]

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

Кстати про M48n21. Ведь при их поиске можно вообще отказаться от факторизации и разместить по всем местам столько малых простых, чтобы неизвестными остались лишь ровно по одному простому в каждой позиции. Искомые числа резко возрастут, вероятность нахождения ещё резче снизится, зато ispseudoprime сильно быстрее numdiv/factor. И что пересилит ещё вопрос.
Как и вопрос искать ли по одному паттерну или сразу по всем. VAL же ищет по одному (или нескольким, не уверен, но точно не по сотням тысяч) и находит, в том числе мировые рекорды, значит и такой подход имеет право на жизнь и может быть выгоднее перебора всех возможных паттернов (как делалось для пентадекатлона M12n15 и некоторых других).

Ищу по нескольким. Счет идет на единицы, максимум на десятки.

По поводу, что выгоднее: увеличивать количество простых или заморачиваться с факторизацией.
Три c половиной года назад мы это обсуждали. На основании накопленной статистики пришли к выводу, что для поиска 20-ки выгоднее всего 3 простых.
Конечно, этот рецепт не обязан быть универсален. Но мои поиски других относительно длинных цепочек показывают, что там, где паттерн с 3-я простыми возможен, он обычно срабатывает быстрее всего.

[Yadryara]

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

Так: if(p%3==2,1,-1) но ускорения нет, я проверил.

Это обычный иф, да.

Его необычность (для меня) в том, что оказывается его можно прямо прибавить, то есть вместо

numdiv(2*p+(-1)^(p%3))==4

можно записать

numdiv(2*p+if(p%3==2,1,-1))==4

У меня эта более длинная конструкция работает чуть помедленнее.

VAL в сообщении #1703161 писал(а):

На основании накопленной статистики пришли к выводу, что для поиска 20-ки выгоднее всего 3 простых.

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

Поднимите руки, кто кроме меня и Дмитрия понял о чём здесь речь. Какие такие 3 простых и в чём выгода?

[VAL]

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

Поднимите руки, кто кроме меня и Дмитрия понял о чём здесь речь. Какие такие 3 простых и в чём выгода?

Хотел поднять руку, но не нашел соответствующего смайлика.

[Yadryara]

wrest, как относитесь к тому чтобы перейти от 4 делителей сразу к 48? Сможете ли написать прогу, чтобы найти например цепочку длиной 10...

[waxtep]

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

waxtep конечно же ещё заглядывал. Вот, кстати и спрошу. Вы дважды пытались с кортежами позаниматься, но не очень сложилось. Задачи показалось слишком сложными? Хотя может и по другим причинам мог интерес пропасть.

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

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

[wrest]

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

Сможете ли написать прогу, чтобы найти например цепочку длиной 10...

Нет, но цепочку из 4-х могу, начинается с 114811332

[Yadryara]

waxtep в сообщении #1703199 писал(а):

Про тройку простых,

А теперь уже я не догоняю, что за тройка простых.

Вы на чём проги пишете, если не секрет?

wrest, тоже неплохо

Для цепочек длиной от 10 с 12-ю делителями обязательным было число $32p$. А нет ли аналогичного обязательного числа для длинных цепочек с 48-ю делителями?

[waxtep]

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

Поднимите руки, кто кроме меня и Дмитрия понял о чём здесь речь. Какие такие 3 простых и в чём выгода?

Тройка простых - это ответ на Ваш вопрос о том, понятно ли, о чем речь.
Пишу на PARI/GP, любительски конечно; когда-то давно любил Matlab, для ДУЧП и всякой расчетной физики. C++, C, ASM последний раз в руки брал вообще совсем давно

[Yadryara]

Боюсь, что не поняли всё же. Вот мы только что искали цепочки и там были не тройки простых, а двойки. Заменю маленькую букву $p$ на $P$, чтоб эти двойки заметны были:

  1-e   2-e   3-e       qr mod 12
   qr    2P    3P               1
   3P    2P    qr              11

То есть в каждой искомой тройке есть ровно два числа, для каждого из которых остаётся найти лишь одиночное простое $P$.

waxtep в сообщении #1703205 писал(а):

Пишу на PARI/GP, любительски конечно;

Отлично. Мы вроде все здесь любители.

[waxtep]

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

Боюсь, что не поняли всё же

Не бойтесь, все норм, - так и понял