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

[Yadryara]

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

Я пытался почти ей заниматься: брал паттерн с размещёнными лишь 2,3,5,7,11,13 и считал. Дошёл за полторы недели (в один поток) до 1e23 и понял что пятнашку так не найти.

А Вы проверяли эту прогу в диапазоне $6.6387422053662391209161093\cdot10^{37} - 6.6387422053662391209161094\cdot10^{37}$ ?

Или $6.63874220536623912091610937\cdot10^{37} - 6.63874220536623912091610938\cdot10^{37}$ ?

[Dmitriy40]

По M(36).
Если ограничиться лишь квадратами простых (кроме двойки, которая в 8-й степени), то у меня получается 1264 группы, и в них можно расставить от 12 до 16 малых простых. Даже $12!$ это слишком много. Потому я ограничился лишь центральными 11-ю числами и лишь двумя группами, в каждой по 8 простых, при этом проверяемыми стали 8 чисел, к сожалению не непрерывных. Всего получается 5040 паттернов, это уже нормально. Модуль/шаг чуть меньше 1.1e34.
Тестовый запуск одного из них показал что можно перебирать с шагом 1е42 за примерно секунду на паттерн, при этом за десяток секунд находятся в том числе и цепочки ALL (valids=8), одна штука. Найдётся ли длинная не знаю, но статистика наберётся, а уж формулы вероятностей выведем.

-- 08.04.2022, 15:56 --

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

А Вы проверяли эту прогу в диапазоне $6.6387422053662391209161093\cdot10^{37} - 6.6387422053662391209161094\cdot10^{37}$ ?

Ну разумеется нет, ей считал до 20 февраля, и за полторы недели не нашла ни единой 11 или больше, только 33шт valids=10. Т.е. КПД поиска никакой.
Вы сомневаетесь что она найдёт цепочки если её точно на них натравить? Вообще-то цепочки ALL должны находится любыми прогами ... За что их и люблю.

[EUgeneUS]

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

Вы уверены что не путаете с пробелами в пути?

Как минимум, не выдало ничего в окно с командной строкой, откуда запускал. Системные логи винды не смотрел.

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

-- 08.04.2022, 15:58 --

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

Ну и раз я привёл конкретный выхлоп, то любое отличие от него считать ошибкой.

Это - да, конечно.

[Yadryara]

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

Вы сомневаетесь что она найдёт цепочки если её точно на них натравить?

Конечно. Проверка и перепроверка - важные вещи. Только я никак не могу для себя решить, что же важнее проверка перепроверки или перепроверка проверки...

[Dmitriy40]

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

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

Вы сомневаетесь что она найдёт цепочки если её точно на них натравить?

Конечно. Проверка и перепроверка - важные вещи. Только я никак не могу для себя решить, что же важнее проверка перепроверки или перепроверка проверки...

Не найдёт: пятнашка найдена по другому паттерну (и зеркальному, и $11^2$ и $13^2$ на других местах). Соответственно не понимаю зачем запускать. Впрочем, вот:

T:\>gp64 -q "M12my1.gp"
Mod(539651641, 1030629600)
66387422053662391209161093000000000000 - start
66387422053662391209161094000000000000 - stop
Error: overflow in input number!
N=0, 0.033s / 0.000s in PARI

Причина: $6.6387422053662391209161093\cdot10^{37}/1030629600>2^{64}$.
И это ещё шаг учитывал и $11^2$ и $13^2$, если и их убрать из паттерна, то шаг будет всего $50400$ и предел проверки не более $50400\times2^{64}\approx9.3\cdot10^{23}$.

[Yadryara]

Dmitriy40, понятно.

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

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

Например, можно заменить подквадратное число 37 на 41 и шаг возрастёт на 22%. Это минимальное изменение шага. Затем снова всепаттерный поиск с самых низов до 15-шки или до $6.639\cdot10^{37}$.

Что нужно изменить в Асмовском исходнике, чтобы её реализовать? Неужели ничего?

А в номере паттерна заменить 6 на 7.

[Dmitriy40]

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

Что нужно изменить в Асмовском исходнике, чтобы её реализовать? Неужели ничего?

Ничего. Программа понятия не имеет про все эти подквадратные числа и прочее. Она делает очень простую вещь: для прямоугольной матрицы 1400х11 (примерно) проверить что все эти числа не равны нулю. Если хоть одно равно, то поэлементно сложить эту матрицу с другой матрицей по модулю третьей матрицы (с простыми числами) и повторить проверку (это будет следующий $k$ из формулы $n=n_0+km$). Всё. Остальное уже частности оптимизации. Программа даже про прямоугольность и двухмерность матрицы не знает, она для неё просто линейный вектор.
Вся остальная сложность убрана в PARI программу по генерации первых двух матриц (начальных значений остатков и приращения остатков при переходе к следующему $k$).
Потому кстати не требуется и коррекция программы для поиска M36. Хоть длины 15, хоть любой другой. Изменятся (возможно, не обязательно) лишь размеры вектора и всё, а даже чем именно он наполнен — дело программы на PARI, а не моей программы.
Повторю, вся реализованная в проге математика описывается двумя простейшими формулами для замены разложения на множители или проверки псевдопростоты — сложение по модулю и проверка на равенство, всё. Именно эти две операции проверяют наличие нулевых остатков по модулю малых простых, т.е. фактически наличие таких делителей в разложении чисел. Остальное — прерогатива программирования. Ещё и поэтому не понимаю как об этом писать в математической статье.
Я выше показывал код на PARI, функционально эквивалентный моей программе, когда про видюхи спрашивал. Всего три цикла с двумя формулами. Вот именно так программа и работает, в первом приближении.
И кстати асм не является строго необходимым, Intel для C (и С++) поставляет инстриксы, т.е. фактически макросы, позволяющие вставлять в код на С конкретную команду процессору, но в виде функции с параметрами, не заморачиваясь распределением переменных по регистрам. Т.е. знать ассемблер не обязательно. А вот внутреннюю архитектуру процессора и систему команд — почти обязательно, чтобы понимать что за команду где и как и почему применить, иначе высокой скорости не добиться. Правда лично у меня сохраняется предубеждённость против такого подхода, как-то я ещё не привык что компиляторы для x86/x64 архитектуры стали достаточно умными/вменяемыми и генерят в общем вполне хороший код. Похуже написанного руками, но уже не в разы. Не привык потому что для всех интересующих меня архитектур (дешевые микроконтроллеры) результат компиляции по прежнему ужасен.

[Yadryara]

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

Программа понятия не имеет про все эти подквадратные числа и прочее.

Хорошо, я сам нашёл тот Ваш пост и перечитал его. Неужто 46080 экзешных прог-32, которые сейчас в облаке, несмотря на номера паттернов не заточены именно под подквадратные 17-37 ?

Неужто достаточно самостоятельно переделать джипишный файл? Ведь номер паттерна нужен только нам(для сравнения), а компу на него наплевать: он 15-шку и так найдёт, даже если у паттерна номера вообще не будет?

V-файлы надо переписать. И $n_0$ надо как-то брать из чинес...

[Dmitriy40]

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

Неужто 46080 экзешных прог-32, которые сейчас в облаке, несмотря на номера паттернов не заточены именно под подквадратные 17-37 ?

Заточены конечно. Но не кодом программы, а подключаемым внешним файликом с таблицами, который формирует программа на PARI (а первые два я руками с калькулятором писал). И в процессе компиляции асм исходника эти таблицы интегрируются в .exe. И думать как подправить код под каждый паттерн не нужно, он одинаков, а таблицы генерятся тоже программой автоматически прямо по паттерну (в ней есть несколько настроечных параметров, но для паттернов одного множества типа КМК37-11 они одинаковы).
Из-да глубокой оптимизации это лишь в первом приближении, на самом деле не совсем так, ради скорости применяются пара хитрых трюков и при глобальной смене паттернов приходится внимательно проверять остаются ли они в силе. Некоторые коэффициенты (не из паттерна, например количество проверяемых простых) ради упрощения кода "зашиты" в программу (в смысле тоже берутся из внешнего файла, но должны быть известны на момент компиляции, а не запуска).
Так что на имя .exe/.v всем конечно наплевать, оно нужно только для различения паттернов между собой и для соответствия им правильного вектора $v[i]$ уже потом в PARI, можете их переназвать как угодно, но просто переписать файлы .v недостаточно, требуется изменить таблицы для каждой программы и перекомпилить.

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

Неужто достаточно самостоятельно переделать джипишный файл?

Да: переделать, запустить для каждого паттерна и результат работы скомпилить в .exe. Только не тот .gp что потом цепочки проверяет и выложен, а тот что генерит таблицы для асм исходника, те самые начальные остатки $(n_0/v[i])\bmod p[i]$ ($v[i]$ это коэффициенты в паттерне) по каждому простому $p[i]$ и таблицу $(m/v[i]) \bmod p[i]$ приращений этих остатков при увеличении $k$ на единицу. Программе же нужно знать как меняются остатки каждого из 11-ти чисел по каждому простому при увеличении $k$. Собственно только это ей и надо знать ...
В принципе когда цифра в 45Г на все программы пугала я даже думал сделать эти таблицы во внешнем файле и читать их оттуда в своей программе (передав ей номер паттерна в каком-нибудь удобном формате), но прочитать файл на асме не тривиально, да и скорость чуть упадёт (второй доступ к диску, хотя конечно закэшируется). Но скорее просто стало лень. Зато можно было бы обойтись всего двумя файлами: маленьким .exe и большим с таблицами (не текстовыми).

-- 08.04.2022, 22:02 --

Досчитал все пропуски и в 6e37, и в 9e37, новых пятнашек не нашёл.
Интервал 0-7e37 есть полностью, сам 7e37 фрагментами, 8e37 нет вообще, 9e37 есть полностью. Все полные выложил в облако, при этом заменил и ранее выложенные для единообразия (укоротил название файла/паттерна). Приступил к досчёту 7e37 и 8e37, должно хватить 3-3.5 суток, примерно к утру 12.04.

[Yadryara]

Спасибо. То есть всё равно придётся 46080 файлов перекомпилить?

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

Приступил к досчёту 7e37 и 8e37, должно хватить 3-3.5 суток, примерно к утру 12.04.

Но теперь-то зачем?? Только для статистики?

Уж лучше(после замены 37 на 41) ещё одну 15-шку в самых низах поискать. Тем более, что kotenok gav готов помочь. Может и Артём не откажется. А чтобы 15-ку не прозевали, надо, например, помечать её вставкой пустой строки.

[Dmitriy40]

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

То есть всё равно придётся 46080 файлов перекомпилить?

Перекомплитить да. Но если есть генератор паттернов или хотя бы просто их список, то это процесс автоматический (если паттерны принадлежат одному подклассу типа КМК37-11), проверил первый, потом нажал кнопку, подождал, получил результат. Это не руками менять все 46080 файлов с рсиком опечаток и времени на это.

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

Но теперь-то зачем?? Только для статистики?

Да, пусть уж будет непрерывный кусок до 1e38.


Всё равно по M36 пока непонятно что считать. Та идея про 5040 паттернов не взошла, за полтора часа из 3340+ цепочек ни одна не имеет правильных делителей хотя бы в одном из непроверяемых мест. Похоже с паттернами я напортачил. Думаю вернуться к идее с 5-ми и 8-ми степенями, чтобы уменьшить количество вариантов паттернов. Числа будут огроменными, но моей программе на это начхать, а PARI ... будет мучиться.

[Yadryara]

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

Но если есть генератор паттернов или хотя бы просто их список, то это процесс автоматический (если паттерны принадлежат одному подклассу типа КМК37-11), проверил первый, потом нажал кнопку, подождал, получил результат.

Конечно. Как назвать-то этот подкласс ? К41-11 нельзя, ибо не указано какое число заменяется. Может просто 11-22 ? 11 одиночных простых и шаг на 22% больше минимального.

Чем раньше найдётся новая 15-ка, тем быстрее будут завершаться новые проверки. Даже если не найдётся, они будут завершаться всё быстрее и быстрее. Но она найдётся, против тервера не попрёшь.

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

[VAL]

19 есть!!!
5908388043825578351730345292813071711296723319324

[EUgeneUS]

VAL
Поздравляю!
$\times 19$

[Yadryara]

Поздравляю с очередным мировым рекордом!

Это 48 делителей.

К вопросу о предчувствиях. Вот они:

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

Но получение набора из 19 чисел вполне реально и без этого.

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

Ведь потом на основе подобных программ можно будет побиться не только за 15-шку, но и за другие мировые рекорды. 19-ку найти, например.

Ну и мой прогноз о том, что начнётся разброд и шатание, тоже сбылся. Кто-то 12-ю делителями по-прежнему занимается, кто-то 36-ю, а кто-то 48-ю.