2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1 ... 238, 239, 240, 241, 242
 
 Re: Пентадекатлон мечты
Сообщение14.10.2025, 08:27 
Аватара пользователя
Yadryara в сообщении #1705812 писал(а):
Медленнее разве что основной комп Дмитрия,

И мой\мои :roll:

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 оптимизацию в ифах? То есть прекратит ли он считать все остатки, в случае неудачи в начале? Если нет, или нет уверенности, то это нужно делать руками.

 
 
 
 Re: Пентадекатлон мечты
Сообщение14.10.2025, 09:31 
Аватара пользователя
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. Дмитрий ранее предлагал ещё проверку делать биттестом. Я об этом вспомнил и попытался применить. И именно на практике обнаружил, что выигрыш по времени происходит, когда биттестом проверяешь разрешённые остатки, а не запрещённые. И именно для моего компа это даёт ускорение. Даже несмотря на огромные числа.

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

 
 
 
 Re: Пентадекатлон мечты
Сообщение14.10.2025, 10:12 
Аватара пользователя
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. Немного зависит от того, как обрабатываются разрешенные остатки по модули три.
Если всё, что выше задано, то это константа.

 
 
 
 Re: Пентадекатлон мечты
Сообщение14.10.2025, 11:22 
Аватара пользователя
EUgeneUS в сообщении #1705822 писал(а):
А известно ли во сколько раз быстрее работает isprime, чем factor для чисел $10^{48} ... 10^{53}$?


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

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

 
 
 
 Re: Пентадекатлон мечты
Сообщение14.10.2025, 11:41 
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}$

 
 
 
 Re: Пентадекатлон мечты
Сообщение14.10.2025, 14:33 
Аватара пользователя
EUgeneUS в сообщении #1705822 писал(а):
Избавление от умножений в цикле реализовано?

Вроде не реализовано. Я внимательно в эту сторону пока не смотрел.

Всё ещё не дошли руки наладить автоматизированный сбор статистики. 8 потоков пока работают. Картина по слабым приближениям уже более-менее понятная:

Код:
0 — 1e51

Valids         7 8 9   10   11   12   13   14   15   16   17   18   19   20   21
Приб    123        2    3         2    4    1    2    1                               15

Приб    124      4 1    1    4    4    4    1         1                               20
Приб    125    1   1    2    3    4    7    2    5    3                               28
Приб    126      1 2    1    5    3    3    2    3                                    20
Приб    127        1         2    5    4    5    2    1    1                          21
Приб    128             3    6    3    3    3    1    3                               22
Приб    129    1 1 2    1    3    1    9    4    3                                    25
________________________________________________________________________________________
               2 6 9   11   23   22   34   18   16    9    1                         151

Верхнюю строчку ещё не досчитал. Из-за того, что она по-прежнему считается для в 10 раз большего диапазона: 0-1e52.

Ещё и в других паттернах найдены приближения. Покажу пока наилучшие:

Код:
                                                                             Valids
178380987012396308863900153677813852686655763044946   1 1111111111111 11  1      17
86174083595630569956285027121743705191886528900946     11 1 1 11111111111 1      16
104294449752115369891319446528628065539537370668946   11  1111111 1 11 1111      16
295415766633890967695868882781142450066682604736146   1 1111111111111  1  1      16
426177122559697931539690746264517602313535884476946   1 11111 11111 11 11 1      16
428302514214814024822755190512136462009263089460946   1111111111 1  1111  1      16
536485877155679109909361726753963129692995263246546   1 1 11111111111 1  11      16
614729180547673494252251341610226140422432039736146   1111 11 111 1 111 111      16
703847910379081045003610200533905190084822515566546   11 1111 11111 1 11 11      16
953802445779976491201723818940647104284640217052946   1 11111 11 11111 1 11      16
954362124827898235312664833988160660856220507278546   1111 11 1 11111 1 111      16
958060655676002182969017719449293633922929570531346   1111111 11 11 11 1 11      16
969753822486232787519188100369583182149298433334546   1111111 111  1111  11      16

 
 
 
 Re: Пентадекатлон мечты
Сообщение14.10.2025, 14:36 
EUgeneUS в сообщении #1705815 писал(а):
б) На всякий случай: делает ли PARI\GP оптимизацию в ифах? То есть прекратит ли он считать все остатки, в случае неудачи в начале? Если нет, или нет уверенности, то это нужно делать руками.
Да, вычисления "ленивые", до первого результата, код if(x>0&&5/x>1,...) работает даже с x=0. Это сделано специально, не столько даже ради ускорения, сколько ради допустимости конструкций типа if(k>0&&v[k]>7,) если k может быть и меньше 1.
EUgeneUS в сообщении #1705815 писал(а):
1. Надо уходить от "давайте поделим на какое-нибудь число, чтобы потом при каждой итерации на него умножать".
Теоретически да, практически смысла мало: вычисление с двумя умножениями p=p1+m*i;n=a*p-20 выполняются за 780нс, а два сложения p+=m;n+=am; выполняются за 700нс. И хотя казалось бы выигрыш более 10%, но это всего 80нс из примерно 3.2мкс на проверку у Yadryara или порядка 2.5%. Сделать можно ибо просто, хотя эффект почти незаметен.
Отказ от вычисления p невыгоден, всё равно же придётся его вычислять, не умножением (сложением), так делением, а это точно медленнее.
Можно даже два других простых тоже вычислять сложениями, а не делениями, вот это даст бОльший эффект, хотя тоже не особо, всего 200нс выигрыш, правда это уже 6.3% от 3.2мкс.
EUgeneUS в сообщении #1705822 писал(а):
А известно ли во сколько раз быстрее работает isprime, чем factor для чисел $10^{48} ... 10^{53}$?
А Вы видели что в программе уже три цикла с factor (третий с numdiv которая тот же factor)? И Вы про какой спрашиваете, наверное про первый как самый часто запускаемый? А он выполняет не factor(), а factor(,30000), что довольно сильно отличается ибо проверяет лишь делители до 3e4 (и этим числом можно ещё и играться ради общей скорости на конкретном диапазоне чисел), зато для всех мест где они возможны и при первой же ошибке кандидат выкидывается.
Плюс и isprime() у нас с Антоном выполняется в другом виде, позволяющем отвергнуть кандидата на 10% быстрее.
И разумеется порядок проверок isprime и factor исследовался и тестировался и выбран быстрейший.
EUgeneUS в сообщении #1705834 писал(а):
Пусть isprime быстрее работает, чем factor, в 100 раз.
isprime() намного быстрее factor() (последний в любом случае делает и isprime, как минимум для проверки последнего числа в разложении, плюс для всех найденных достаточно больших делителей). Но isprime() медленнее factor(,30000) (хотя и быстрее factor(,300000)) - и этим я с Антоном пользуемся.
EUgeneUS в сообщении #1705822 писал(а):
Кстати, тогда уж и тройку туда же: Из остатков по модулю $15015$ живых будет $5760$.
Тройка обычно учитывается вместе с двойкой при умножении lcm(v)*6 и коррекции p1 (тот самый +5/6*m).

 
 
 
 Re: Пентадекатлон мечты
Сообщение14.10.2025, 15:00 
Аватара пользователя
Dmitriy40
Спасибо за разъяснения.

Dmitriy40 в сообщении #1705868 писал(а):
И разумеется порядок проверок isprime и factor исследовался и тестировался и выбран быстрейший.

Прекрасно.

Dmitriy40 в сообщении #1705868 писал(а):
А Вы видели что в программе уже три цикла с factor (третий с numdiv которая тот же factor)?

Видел, но мельком. С момента возобновления темы озадачился подсчетом шансов и подробно в оптимизации кода не разбирался.
Кстати, а откуда можно забрать текущую версию со всеми оптимизациями?

Dmitriy40 в сообщении #1705868 писал(а):
Тройка обычно учитывается вместе с двойкой при умножении lcm(v)*6 и коррекции p1 (тот самый +5/6*m).


Это я помню. И уже отмечал, что такая работа с тройкой выбрасывает половину "хороших" цепочек и увеличивает $N$ как минимум в два раза.
Вчера показывал с числами, как это влияет на примере $D(12.15)$, чуть позже выложу для $D(48,21)$

 
 
 [ Сообщений: 3623 ]  На страницу Пред.  1 ... 238, 239, 240, 241, 242


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group