Пентадекатлон мечты

[EUgeneUS]

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

Медленнее разве что основной комп Дмитрия,

И мой\мои

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

И в одном потоке. И на моём компе.

Это понятно.

Некоторые предложения по ускорению (сорри, если уже сделано).

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

$n=n_0 + 6 \cdot \text{LCM} \cdot i$, всё тоже самое, но минус одно умножение в цикле.
$n_0$ и $\text{LCM}$, конечно заранее посчитали.

От второго умножения тоже можно избавиться:
$n_{i+1}=n_i + 6 \cdot \text{LCM}$, только прибавлять нужно для каждого $i$ (до длинного ифа), а умножать можно для 40% из них (после длинного ифа).

2. Оптимизация длинного ифа.
а) для простых $5, 7, 11, 13,$ можно заранее составить список запрещенных остатков по модулю $5 \cdot 7 \cdot 11 \cdot 13=5005$, и проверять эти остатки за одно вычисление модуля по $5005$ и за одну проверку в списке. Это вроде бы должно быть быстрее, чем четыре раза считать модуль. Но не уверен.

б) На всякий случай: делает ли PARI\GP оптимизацию в ифах? То есть прекратит ли он считать все остатки, в случае неудачи в начале? Если нет, или нет уверенности, то это нужно делать руками.

[Yadryara]

EUgeneUS в сообщении #1705815 писал(а):

На всякий случай: делает ли PARI\GP оптимизацию в ифах?

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

Да, немало идей уже реализовано. Например:

EUgeneUS в сообщении #1705815 писал(а):

2. Оптимизация длинного ифа.
а) для простых $5, 7, 11, 13,$ можно заранее составить список запрещенных остатков по модулю $5 \cdot 7 \cdot 11 \cdot 13=5005$, и проверять эти остатки за одно вычисление модуля по $5005$ и за одну проверку в списке. Это вроде бы должно быть быстрее, чем четыре раза считать модуль.

Две идеи, которые предложил впс, уже отрабатывались.

1. Можно вообще не выполнять терапевтику (проверку в длинном ифе) самых важных, самых маленьких модулей, а попросту разбивать программы на части. Например, по модулю 5 не проверять, а экономить 20% перебора, запуская 4 программы.

2. Объединение модулей. Вы тоже об этом подумали.

И обе идеи дают ускорение. И нужна балансировка для каждого компа.

3. Дмитрий ранее предлагал ещё проверку делать биттестом. Я об этом вспомнил и попытался применить. И именно на практике обнаружил, что выигрыш по времени происходит, когда биттестом проверяешь разрешённые остатки, а не запрещённые. И именно для моего компа это даёт ускорение. Даже несмотря на огромные числа.

Ну и таких примеров масса.

[EUgeneUS]

Yadryara
ИМХО, не нужно адаптировать по каждый комп.

А известно ли во сколько раз быстрее работает isprime, чем factor для чисел $10^{48} ... 10^{53}$?

-- 14.10.2025, 10:13 --

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

Да, немало идей уже реализовано.

Избавление от умножений в цикле реализовано?

-- 14.10.2025, 10:18 --

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

1. Можно вообще не выполнять терапевтику (проверку в длинном ифе) самых важных, самых маленьких модулей, а попросту разбивать программы на части. Например, по модулю 5 не проверять, а экономить 20% перебора, запуская 4 программы.

Из остатков по модулю $5005$ живых будет $2880$, можно их посчитать (один раз для каждого паттерна), а потом перебирать автоматически.

-- 14.10.2025, 10:23 --

EUgeneUS в сообщении #1705822 писал(а):

Из остатков по модулю $5005$ живых будет $2880$, можно их посчитать (один раз для каждого паттерна), а потом перебирать автоматически.

Кстати, тогда уж и тройку туда же: Из остатков по модулю $15015$ живых будет $5760$.

-- 14.10.2025, 11:06 --

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

И пониже посмотрю. Это же не константа, параметры поиска можно и нужно варьировать.

Это не константа в том смысле, что зависит:
0. От того, какую цепочку ищем и по какому типу паттернов.
1. От желаемой вероятности найти цепочку.
2. От количества паттернов.
3. Немного зависит от того, как обрабатываются разрешенные остатки по модули три.
Если всё, что выше задано, то это константа.

[EUgeneUS]

EUgeneUS в сообщении #1705822 писал(а):

А известно ли во сколько раз быстрее работает isprime, чем factor для чисел $10^{48} ... 10^{53}$?

Поясню откуда вопрос.
Пусть isprime быстрее работает, чем factor, в 100 раз.
Тогда после проверки на простоту обязательных простых, нужно проверять на простоту остальные числа (18 штук), до первого попадания в простое.

Тогда за $18/100$ от времени факторизации, получаем дополнительную фильтрацию перед отправкой на факторизацию $0.94^{18} \approx 0.328$, в три раза. Даже немного больше.

[vicvolf]

VAL
Критерий допустимости расстояния $d$

Для $A_1 = 2^{34}, A_2 = 3^{34}$:

$d$ допустимо ⇔ ∃ простые $p, q$: $3^{34}q - 2^{34}p = d$

Минимальное допустимое расстояния $d$:
$d_{\text{min}} = 3^{34}\cdot 2 - 2^{34}\cdot 3 \approx 3.3\times 10^{16}$