Симметричные кортежи из последовательных простых чисел

[Dmitriy40]

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

Вместо того, чтобы делить 10 раз на 5 можно 10 раз умножить на 3 и по остаткам из таблицы умножения по модулю 5 как раз и определить, что годятся только 4 числа: $ 2, 8, 22, 23 $.

А я наоборот, как раз не понял. Вроде и умножать надо не на 3, а на 5. И таблица остатков по модулю 5 тогда нужна не до 5, а до 35. А если будем умножать модуль 510510 на 19? Таблица остатков по модулю 19 понадобится почти до 10млн?! Для пояснения ручного счёта может и сойдёт, но применять ...

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

Здесь 6 значений.

Не все они нужны, и нужны не эти. Если КТО вычислять последовательно, то нужны (1/2)%3, (1/6)%5, (1/30)%7 (так обозначу обратный элемент). При другом способе вычисления КТО нужны (1/105)%2, (1/70)%3, (1/42)%5, (1/30)%7.

[Yadryara]

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

А я наоборот, как раз не понял.

Значит я прав, что начал с кубиков, с крошечных чисел. Если уж мы тут друг друга понять не можем...

$\tikz[scale=.08]{ \fill[green!90!blue!50] (20,120) rectangle (30,140); \draw[step=10cm] (0,110) grid +(40,40); \node at (5,145){\text{1}}; \node at (15,145){\text{2}}; \node at (25,145){\text{3}}; \node at (35,145){\text{4}}; \node at (5,135){\text{2}}; \node at (15,135){\text{4}}; \node at (25,135){\text{1}}; \node at (35,135){\text{3}}; \node at (5,125){\text{3}}; \node at (15,125){\text{1}}; \node at (25,125){\text{4}}; \node at (35,125){\text{2}}; \node at (5,115){\text{4}}; \node at (15,115){\text{3}}; \node at (25,115){\text{2}}; \node at (35,115){\text{1}}; }$

Из этой ТУ по модулю 5 видно, что только при умножении разрешённых остатков на 3, получаются 1 и 4.

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

Если КТО вычислять последовательно, то нужны (1/2)%3, (1/6)%5, (1/30)%7 (так обозначу обратный элемент). При другом способе вычисления КТО нужны (1/105)%2, (1/70)%3, (1/42)%5, (1/30)%7.

Обдумаю.

-- 24.01.2024, 14:00 --

(1/30)%7 — это обратный элемент к 30 по модулю 7 ??

[Dmitriy40]

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

(1/30)%7 — это обратный элемент к 30 по модулю 7 ??

Да. Mod(1/30,7) в PARI.

-- 24.01.2024, 14:53 --

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

Из этой ТУ по модулю 5 видно, что только при умножении разрешённых остатков на 3, получаются 1 и 4.

Из Технического Условия? Ну если из него, то конечно, априори.
И нет, мне не видно: 1 и 4 в таблице ещё кое-где встречаются. И куда делись остатки 0 и главное 1?! По модулю 5 должно быть ровно 5 возможных остатков. И почему на 3, а не на 2, в колонке левее тоже и 1 и 4 есть? Вообще непонятно при чём тут таблица умножения по модулю. Может я и туплю конечно.
Ваша экономия буковок только вредит пониманию.

[Yadryara]

ТУ — таблица умножения, да. Только без нулей.

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

Ваша экономия буковок только вредит пониманию.

Я сразу понял что МК у Вас это не "Московский Комсомолец". Но какое-то время думал что МикроКалькулятор. Потом решил, что это скорее Машинный Код.

Почему умножаю на 3:

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

Обратный элемент числа $5$ по модулю $7$ равен $3$.

Вместо деления на 5 умножил на 3 и увидел, что по указанному признаку можно оставить те самые 4 числа из 10.

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

и потом сделать 16 умножений и 8 делений

А без делений точно нельзя?

[Dmitriy40]

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

А без делений точно нельзя?

Можно конечно. В какой теме я написал как КТО вычисляется? Повторю формулу: r[]%(M=Mx*My)=x[]+Mx*(((y[]-x[])*d)%My), d=Mod(1/Mx,My). Смотрим на ((y[]-x[])*d)%My и пытаемся отказаться от %: ((y[]-x[])*d)%My = (y[]*d-x[]*d)%My = ((y[]*d)%My-(x[]*d)%My)%My. Теперь в скобках оба слагаемых (которые вычитаются одно из другого) можно подсчитать заранее, просто хранить в векторах не x[],y[], а сразу вон те выражения. При вычитании же двух остатков по одному модулю может получиться либо неотрицательное число меньше модуля (и тогда %My делать и не нужно), либо отрицательное, по абсолютной величине меньше модуля (и тогда %My можно заменить на просто +My). Т.е. вычитаем два вектора, сравниваем элементы с нулём (на отрицательность результата), условно добавляем константу (My) и вуаля, обошлись без делений.
Пример на PARI для модуля 7 (в векторах уже пересчитанные x[],y[] от балды):
? x1=[0,1,2,3,4,5,6]; y1=[1,4,0,3,6,2,5]; r=apply(t->if(t<0,t+7,t), y1-x1)
%1 = [1, 3, 5, 0, 2, 4, 6]
Для КТО осталось вектор результата домножить на Mx (результаты при этом трансформируются от модуля My к модулю My*Mx=M) и сложить с вектором x[] (не пересчитанным) (переполнения модуля M произойти не может, ничего проверять не надо). Хранить итого надо три вектора вместо двух: x[], x1[], y1[] (последние два пересчитанные по d и модулям). Выигрыш не очевиден, три вектора той же длины вроде бы больше двух векторов, зато отказались от медленного (в 10-70 раз) деления. Классический размен памяти на скорость.

-- 24.01.2024, 16:06 --

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

Вместо деления на 5 умножил на 3

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

-- 24.01.2024, 16:18 --

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

Выигрыш не очевиден, три вектора той же длины вроде бы больше двух векторов, зато отказались от медленного (в 10-70 раз) деления. Классический размен памяти на скорость.

Ещё один огромный плюс такого варианта последовательного вычисления КТО, что все операции до умножения на Mx можно проводить по модулю My и выбрав его достаточно небольшим (малое простое или небольшое произведение нескольких малых простых) нет нужды привлекать длинную арифметику. Которая понадобится только для умножения на Mx и сложения с x[]. Но если и Mx и My влезают в регистр (ну вот так мы поделили общий M на два взаимнопростых числа), то в процессорах есть команда умножения двух чисел одинарной длины с получением результата удвоенной длины, а уж сложить два результата двойной длины вообще не проблема. И на ассемблере x86 для модулей M меньше удвоенного размера регистров (2^128 для x64) всё получается коротко и красиво (что будет после компиляторов языков высокого уровня я предпочитаю не смотреть чтобы спать спокойнее).

[Yadryara]

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

Всё равно, это место мне кажется нетривиальным.

Так может это и хорошо. То есть я Вас не понял, пошёл не в ту степь и в результате всё равно вырулил куда надо. И ведь на 2 тоже можно умножить. А ведь процу проще на 2 умножить чем на 3? Подумайте, ведь это центральная 5-ка как раз из 19-252.

[Dmitriy40]

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

И ведь на 2 тоже можно умножить.

Не, этого тоже не понимаю: КТО выдаёт однозначный результат по соответствующему модулю (35, 105, 210), никаких разночтений быть не может. У Вас на каждом шаге фактически КТО и вычисляется. Вдруг это (что и на 2 тоже можно) просто артефакт конкретного примера?
Хотя, если результат умножения вектора получится идентичным (только числа в другом порядке), тогда да, наверное можно и на 2 ... Но это требует проверки и обдумывания.

А центральная 5-ка из 19-252 меня не интересует. Как она поможет в ускорении поиска 19-152? По моему никак, только замедлит (как центральная 17-240 из 19-252 замедляет перебор чисел в 5 раз по сравнению с перебором сразу всей 19-252).

[Yadryara]

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

Вдруг это (что и на 2 тоже можно) просто артефакт конкретного примера?

Ну так и пусть! Ведь Вас уже почти год интересует конкретный паттерн.

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

Но это требует проверки и обдумывания.

Вот именно.

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

А центральная 5-ка из 19-252 меня не интересует. Как она поможет в ускорении поиска 19-152?

Ну так я и не предлагаю её отдельно искать. Ведь по-барабану, какое число в этой 19-ке искать, 1-е или 8-е. Так? Так вот, для 8-го числа(1-го в 5-ке) подмечена такая закономерность. Можно это использовать? Может и другие аналогичные закономерности есть, это вопрос сложный.

[Dmitriy40]

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

Так вот, для 8-го числа(1-го в 5-ке) подмечена такая закономерность. Можно это использовать?

Где использовать? Как я понял пока что Вы говорите об расчёте КТО, т.е. в терминах поиска 19-252 это как получить те 6.636e6 чисел в таблице для 37#.
Мне это малоинтересно по причинам:
1. Получение этих чисел намного быстрее получения остатков от них по модулям 30-40 небольших простых (которые и нужны).
2. Эти числа можно вообще получить один раз и просто вставить в программу. Вот таблицу 37# их остатков - не вставишь, это под 400МБ двоичных данных (или под 1ГБ текста). FASM отказывается, а писать код обходящий эту проблему ... как бы он получился не дольше текущего вычисления таблицы на лету (секунды, 400МБ только читаться с диска будут сравнимое время).
3. Как-то эта вот закономерность слишком уж индивидуальна что ли, среди десятков команд экономит лишь одну-две, и не самые медленные.
4. В одном из вариантов программы вся эта таблица 37# (и всех 6.636e6 чисел и их остатков по 40шт разных простых) строится 4с, а потом программа работает около 12ч с этой таблицей. Ускорять эти 4с оставляя 12ч не тронутыми?! Не-не-не. Вот если доберётесь до быстрого построения всех остатков (итерационно или по нескольким меньшим массивам) - это будет прорыв. Ну или если до меня дойдёт как умножение на константу перемешивает остатки и как это можно (и можно ли!) сделать быстро.
Либо я чего-то недопонял.

(О размерах таблиц)

PS. Кстати, раз уж про таблицы вспомнил. Когда-то давно говорил что моя программа может использовать до 200млн строк в таблице (вместо 6.626млн для 37# в поиске 19-252). Но весной 2021 программу доработал и теперь она за счёт выноса части циклов наружу (в запускающую программу, например на PARI) может использовать и больше таблицы, например то что реально работает с апреля 2023 использует эффективный (вся таблица одновременно нигде никогда не существует) размер таблицы 47#=107млрд строк, в 500 раз больше тогдашнего предела. Т.е. таблица получается в виде матрицы 107мдрд строк по 40 колонок по байту, общим размером под 4ТБ. Вот с такими таблицами научился работать три года назад (причём под x32 с ограничением 2ГБ на всю память программы). Программа может и ещё хоть в миллиарды раз больше размеры (например 824e18 строк для 73#), но тогда уже падает эффективность (и скорость перебора, что кстати довольно нетривиальный эффект, ведь должно быть всегда только ускорение).

[Yadryara]

Dmitriy40, просто хочется как-то Вам помочь. Как я понял, Вы с апреля считаете в 1-2 потока и уже очень трудно дать заднюю, а вдруг 19-ка где-то совсем рядом. С другой стороны, оргвопросами с подключением других компов Вы заниматься не хотите и мне это понятно, программировать интереснее чем агитировать. Так что идеи ускорения счёта пытаюсь подбрасывать. Какие-то из них конечно могут быть смешными, ведь я не то что всех, очень многих деталей не знаю.

[Dmitriy40]

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

Заднюю давать нет причин, более реальной задачи я пока не вижу (а когда видел весной-летом от Hugo - то и запускал приостанавливая 19-ку). И да, надеюсь 19-ка где-то рядом, уже несколько месяцев всё рядом и рядом, и никак.

Подключение других компов ... А у кого есть много (с десяток) свободных потоков с AVX?! Помнится почти ни у кого здесь. А Демиса я сагитировал, он с начала декабря помогает.
Переписывать же под SSE идея так себе.

Идеи это прекрасно.
Вот почитал про ваши кубики, обрадовался что можно каждую позицию подбирать подряд (рекурсивный обход дерева с возвратом), только собрался писать код, как пришла мысль в голову что никуда не деться от обхода всех 293.4e15 комбинаций для 67#=7.858e24, а этот рекурсивный перебор простых ну никак не уложится в 1 такт на каждую допустимую комбинацию (про общие вообще молчу), никак. Значит надо не менее 3e17 тактов или около 1000 суток в один поток. Но 1 такт это откровенно от фонаря цифра.
Вообще вот эта цифра, 3e17 комбинаций, убивает почти все идеи на корню: кроме проверки 3e17 вариантов их все надо ещё как-то вычислить. А это КТО в том или ином виде. И сколько ни пытаюсь, все придуманные алгоритмы или сваливаются к уже реализованному, или упираются в умножение на Mx в формуле КТО выше (умножить числа можно, даже в общем векторно, но вот как быстро умножить вектор остатков чтобы он при этом остался вектором остатков по тому же простому - не знаю). Возможно получится раздербанить формулу x[]+Mx*(((y[]*d)%My-(x[]*d)%My)%My), которую можно вычислять без делений, на x[]+Mx*((y[]*d)%My)-Mx*((x[]*d)%My)+if(?,Mx*My) = x[] + A[]-B[]+if(A[]<B[],Mx*My) и тогда вот уже эту конструкцию можно наверное вычислять по разным другим простым модулям (хотя бы 40шт до 256) тоже без делений ... Навскидку тут два сложения по модулю (A[]-B[]+if и потом с x[]), каждое по три команды, 6 команд, 3 такта AVX, на 40шт модулей, 120 тактов, пусть даже сразу 32 числа, 4 такта на число, на 3e17 чисел это 1.2e18 тактов, 10 лет в один поток. И это только КТО с остатками, а ещё надо ведь и проверить что получилось, но похоже быстрее чем сейчас. Впрочем, тут стоит ещё подумать.
Вот видите, даже если идеи и не сработали, то заставили задуматься о другом.

[Yadryara]

Andrey A в сообщении #1627043 писал(а):

Я, простите, не в теме. Если речь о КТО

Это Вы пока не в теме Присоединяйтесь.

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

А Демиса я сагитировал, он с начала декабря помогает.

Надо же молодец какой!

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

никуда не деться от обхода всех 293.4e15 комбинаций для 67#=7.858e24

Конечно, ведь именно это КТО и гарантирует: общее количество допустимых остатков в периоде в точности равно произведению всех таких количеств для каждого простого модуля. Правильно понимаю?

И, при переходе к 71# их будет в 52 раза больше. Но (и летом уже говорил об этом) именно внизу, то есть до 7.858e24 их уже будет меньше, не 293 квадриллиона, а в среднем 215.

Так что деваться-то есть куда, научиться бы только быстро считать эти остатки...

[Dmitriy40]

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

Конечно, ведь именно это КТО и гарантирует: общее количество допустимых остатков в периоде в точности равно произведению всех таких количеств для каждого простого модуля. Правильно понимаю?

Да. И это вроде несложно доказывается: каждый элемент $x$ из вектора по одному модулю $m$ при добавлении нового взаимнопростого c $m$ (не обязательно простого, достаточно взаимной простоты) модуля $p$ задаётся формулой $r=x+m i, i=0\ldots p-1$ и пробегает все возможные остатки по модулю $p$ (это кажется неочевидным, но на то есть теорема, для неё и требуется взаимная простота $m$ и $p$), из которых лишь $k$ являются разрешёнными, т.е. каждый элемент из исходного вектора даёт ровно $k$ новых элементов (но при разных $i$). Т.е. перемножение длин.
Простые модули, да ещё и строго последовательные берутся лишь для упрощения, можно брать любые взаимнопростые.

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

Но (и летом уже говорил об этом) именно внизу, то есть до 7.858e24 их уже будет меньше, не 293 квадриллиона, а в среднем 215.

Да, так. И всё меньше и меньше с каждым новым простым. Вопрос лишь как получить эти 215e15 из всех 15.26e18 (для 71#) не получая даже всех 293.4e15.

Причём в принципе я даже знаю как от 293.4e15 оставить 215e15: для этого достаточно потребовать чтобы на Mx (которое 67#) из формулы выше про КТО умножалось обязательно 0, что возможно только если элемент из x[] (которых 293.4e15) строго равен любому из элементов y[] (которых 52) и тогда такой x подходит. И здесь даже не обязательно сравнивать все 89 (для 71#) битов полного числа, достаточно сравнить младшие 16 битов (8 скорее всего маловато, да и не вычислить их, не все команды есть байтовые) и только если они совпали (что будет ошибочным равенством чисел крайне редко) - проверить и остальные биты. А раз нам не нужны старшие биты чисел x[] для сравнения во внутреннем цикле, то и вычислять их тоже можно лишь младшие 16 битов, т.е. КТО для получения 293.4e15 тоже можно считать только младшие 16 битов, параллельно сразу 8-16 чисел (SSE-AVX). Но сравнить-то надо каждый элемент x[] с каждым элементом y[], т.е. 15.26e18 сравнений. Даже если сравнивать сразу 16 чисел (AVX), то это 1e18 операций только сравнения. Или 5e17 тактов, а это уже больше 4 лет в один поток. Плюс сколько они будут вычисляться. И это только по одному простому (71), а хотелось бы и по 40 простым (до 256), это отсеет почти 80% от 293.4e15. Зато матрицу (размерами 293.4e15 на 40) остатков строить не надо, достаточно вектора (длиной 293.4e15). Зато дальше количество сравнений растёт не как произведение, а как сумма: 215e15 надо сравнить с 54 числами от 73, т.е. всего сравнений 293.4e15*52+293.4e15*52/71*54=293.4e15*52*(1+54/71), менее чем вдвое больше. И для простых с 71 до 256 сумма в скобках 32.3 или 4.9e20 операций сравнения, 260 лет в один поток, только сравнений, без КТО. И всего впятеро уменьшение числа 293.4e15. Как-то снова тухло.
Тоже в общем интересная мысль, тоже надо бы додумать и заценить и время поточнее, и может ещё какая идея стукнет.

-- 25.01.2024, 11:52 --

Для сравнения: сейчас, получив каким-то образом в AVX регистре 32 остатка по малому простому (до 128), я семью командами за 2.33 такта получаю 32 флага допустимости полученных остатков по данному простому. Т.е. сравнения выполняются со скоростью 14 чисел на такт. Хм, более чем вдвое медленнее 16-ти чисел за полтакта однако! Интересненько ... Ошибся где-то что ли ... Или и правда можно ускорить вдвое, да ещё и отказавшись от проблемной огромной матрицы ... Заманчиво.

[Dmitriy40]

Упс, всё же ошибся, сразу в двух местах: и матрица остатков всё же нужна (не делить же элемент вектора на простые 71-256), и количество команд сравнения неправильно посчитал.
Сейчас за 2.33 такта "выполняются" (в смысле что получается идентичный результат) 32*52 сравнений (и 32*108 для простого 127 за то же время). А если сравнивать младшие биты (тоже по 8), то надо 52 (или 108) команды по полтакта, это 26 (или 54) тактов, вместо 2.33. Не вдвое быстрее, а вдесятеро медленнее.
Вот ни в какую не хотят новые идеи работать быстрее ...

Да и про 80% для простых 71-256 тоже просчитался, уже для одного 71 останется 52/71=73%, а до 256 останется лишь 0.5% или примерно 1.5e15.

Никуда от матрицы остатков никак не деться ... Вот как её побыстрее вычислять бы ...

[Dmitriy40]

Похоже да, усложнение формулы вычисления КТО до разбивки её на 4 слагаемых (одно условно) вполне позволяет вычислять остатки по другим простым прямо во внутреннем цикле (фактически в нём линейный проход блоками кратными таблице заменяется проходом только по допустимым вариантам остатков для простых больше засунутых в таблицу). Что забавно, код внутреннего цикла вообще практически не меняется, надо лишь правильно вычислять ему "базу", не линейно, а через КТО.
Там есть тонкость, с условным слагаемым, его учёт требует разбиения одного цикла на три последовательных (не вложенных): точно с этим слагаемым, около точки отмены, точно без него. Но это решаемо.
От перехода с линейного перебора на КТО неприятные следствия: при таком проходе нет привязки к реальным числам и можно найти большее число раньше меньшего; нереально пропустить уже посчитанное, оно будет пересчитываться; нельзя ограничить перебор порогом в реальных числах, будет считаться например все 7.858e24 для 67# и никак иначе. Учёт условия на реальные числа требует добавления кода этой проверки в самый внутренний цикл, что полностью убивает всю скорость перебора.
Но зато приятные следствия - в повышении скорости перебора: для таблицы 37# с 6.636e6 строками до полных 67#=7.858e24 надо перебрать не 41*43*47*53*59*61*67 блоков, а лишь 24*24*2834*40*42*48, в 8 раз меньше (т.е. быстрее). Я вообще собираюсь отказаться от больших таблиц и ограничиться тысяч 20 строк чтобы влезало в кэш L2 каждого ядра, на скорость это уже почти не повлияет (меньше процента). Зато есть надежда что в многопоточной системе будет заметно меньше трафик в кэш L3 и память, что тоже должно поднять скорость от текущей. Плюс короткая таблица позволяет сделать её "шире" (больше остатков хранить в каждой строке) и соответственно немного быстрее проверять на делимость на простые: сейчас на AVX проверяются простые лишь до 256, остальные обычным кодом, но AVX код отфильтровывает лишь 200:1 (уменьшает количество вариантов с 6.636e6 до 34e3) в среднем за расчётных 3 такта на строку таблицы, остальные же проверки добавляют ещё столько же (до 6 тактов на число/паттерн/цепочку), хотя должны бы выполняться за максимум полтакта в сумме, перенос и этого кода в асм должен дать ещё 1.5 раза выигрыш скорости.
Правда я не до конца уверен в правильности перехода y[]<x[] => A[]<B[], это ещё надо бы проверить. Но даже и его нарушение - решаемо.
Так что буду писать и тестировать скорость.