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

[Dmitriy40]

Yadryara
Что означает выражение "цепочки правильно считаются"? Подсчитывается их количество (как я подумал)? Или проверяется что цепочка именно непрерывная 14-ка? Или подсчитывается её вероятность? И на основании чего, формулы или статистики? По формулам любые цепочки должны считаться правильно, чем тут непрерывные 14-ки выделены?! Статистика же без ALL не даёт правильного количества цепочек, и даже с ALL не даёт (хотя погрешность сильно меньше), вот вероятность от противного, не быть цепочкой, видимо даёт.

[Yadryara]

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

Что означает выражение "цепочки правильно считаются"?

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

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

То есть для непрерывных 14-к нет потерь в большом ифе.

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

Подсчитывается их количество (как я подумал)?

Да, их количество считается правильно именно в том смысле, что нет потерь в большом ифе. А потери в ехе уже учтены при расчёте вероятности.

[Dmitriy40]

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

То есть для непрерывных 14-к нет потерь в большом ифе.

Есть (если не закомментирована часть проверок): ispseudoprime обязательно сработает на один из краёв, даже если другой край даст ровно 12 делителей в непроверяемом месте и такая непрерывная 14-ка с ошибкой в проверяемом месте найдена не будет.
Нет, если края закомментированы в if, то разумеется найдутся все 14-ки после exe, но тогда найдутся и все 13-ки и все 12-ки (мы же по три места с каждого края комментировали), в чём тут уникальность 14-ки то?

Не очень я понимаю как Вы учли потери в exe, ведь после него уже нет никакой информации сколько возможных непрерывных 14-ок отсеялось так как имели малые простые делители на проверяемом краю, но ладно, это уже не столь существенно.

[VAL]

Обещал прокомментировать. Комментирую.

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

Потому что выбирать одну-две группы паттернов и один из 10! вариантов в них ради сокращения программ хотя бы до сотни тысяч — это проверка по вершинам, которая результата не принесла.

Проверка "по вершинам", по-видимому, действительно не самый эффективный подход (хотя и тут может повезти).
Но разве то, что описано выше, это "по вершинам". Это "плоскогорье".
И действовать, IMYO, надо именно так. Мы ведь не единственную цепочку ищем.
Тут уже упоминалась 47-страничная таблица (на самом деле там больше страниц, рядом ссылка на продолжение). Так вот, большинство результатов в этой таблице найдены поиском всего по ОДНОМУ паттерну.
Всякий раз я сначала высчитывал эмпирически примерное число проверок для нахождения требуемой цепочки. И если оно не превышало $10^{11}$ запускал один паттерн. И всякий успешно.
И только при более долгом поиске начинал параллелить.

В случае отыскания цепочек из чисел по 36 делителей параллелить придется (без этого реально отыскать, разве что, цепочку из 12 чисел).
Полагаю, разумно разбить поиск на две части. Сначала искать цепочку из 13 чисел (12 найдутся по ходу). А в случае не слишком трудозатратного успеха искать 15 чисел (14 по ходу). Для 13 чисел могу предоставить 384 паттерна, которые кажутся мне наиболее перспективными. Уверен такой ширины захвата достаточно.

Цепочка из 20 чисел по 48 делителей, весьма вероятно, найдется в ближайшее время (даже если Лев не "раскошелится" хотя бы на один поток ). Только за сегодня нашел еще две цепочки по 19 чисел.

[Dmitriy40]

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

Для 13 чисел могу предоставить 384 паттерна, которые кажутся мне наиболее перспективными. Уверен такой ширины захвата достаточно.

384 паттерна или 384 группы по x! паттернов в каждой? Всё равно давайте, посмотрим, будет что считать.
У меня мыслей как выбирать перспективные паттерны пока так и не появилось.

[VAL]

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

384 паттерна или 384 группы по x! паттернов в каждой?

384 паттерна. Это $2\cdot 2\cdot 2\cdot 2\cdot 24$
Сейчас оформлю наглядно.

-- 18 апр 2022, 19:15 --

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

Сейчас оформлю наглядно.

Пока оформлял, ошибку нашел
Будем править.

[Yadryara]

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

Есть (если не закомментирована часть проверок)

Так написал же что закомментированы:

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

Большой иф специально настроил так же как у Вас.
if(
\\! (z[1]>0 && !ispseudoprime((n+0)/v[1])) ||
\\! (z[2]>0 && !ispseudoprime((n+1)/v[2])) ||
\\! (z[3]>0 && !ispseudoprime((n+2)/v[3])) ||
(z[4]>0 && !ispseudoprime((n+3)/v[4])) ||
(z[5]>0 && !ispseudoprime((n+4)/v[5])) ||
(z[6]>0 && !ispseudoprime((n+5)/v[6])) ||
(z[7]>0 && !ispseudoprime((n+6)/v[7])) ||
(z[8]>0 && !ispseudoprime((n+7)/v[8])) ||
(z[9]>0 && !ispseudoprime((n+8)/v[9])) ||
(z[10]>0 && !ispseudoprime((n+9)/v[10])) ||
(z[11]>0 && !ispseudoprime((n+10)/v[11])) ||
(z[12]>0 && !ispseudoprime((n+11)/v[12])) ||
\\! (z[13]>0 && !ispseudoprime((n+12)/v[13])) ||
\\! (z[14]>0 && !ispseudoprime((n+13)/v[14])) ||
\\! (z[15]>0 && !ispseudoprime((n+14)/v[15])) ||

Неужто не видно, что закомментированы именно по три крайних.

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

если края закомментированы в if, то разумеется найдутся все 14-ки после exe, но тогда найдутся и все 13-ки и все 12-ки (мы же по три места с каждого края комментировали), в чём тут уникальность 14-ки то?

Я разве что-то писал про уникальность 14-ки?

Я сравнивал непрерывную 14-ку с любой 14-кой. Я не сравнивал её ни с 13-кой, ни с 12-кой.

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

Не очень я понимаю как Вы учли потери в exe, ведь после него уже нет никакой информации сколько возможных непрерывных 14-ок отсеялось так как имели малые простые делители на проверяемом краю,

Да так и учёл. Я же ведь считал вероятность конкретно для Вашей программы. Да, я не знаю, сколько именно отсеялось. Но это не всегда нужно знать.

Ну вот представьте, что Вы пришли играть в рулетку. На барабане 35 чисел. Что же это за рулетка такая??

"А" - говорит пит-босс - "мы её переделали из той, что была раньше." А какая она раньше-то была - американская(38 чисел) или европейская(37) ? Нужно ли Вам это знать для расчёта вероятностей? Не-а. Надо брать 35 как данность и считать.

[VAL]

После правки получилось $2\cdot 6 \cdot 24 = 288$ паттернов.
Вторая табличка просто отзеркалена.
Синевато-сероватые пары перестановочны между собой, а зеленоватые - между собой.
Мне представляется, что менять множители именно парами чуть перспективнее.
Но в принципе можно и поодиночке. Тогда получится $2\cdot 6! \cdot 8! = 58060800$ паттернов.

[Dmitriy40]

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

А какая она раньше-то была - американская(38 чисел) или европейская(37) ? Нужно ли Вам это знать для расчёта вероятностей? Не-а.

Конечно же надо: смотря как переделали, сделали все 35 чисел равновероятными или одно-два числа вдвое-втрое более вероятны (если лишние просто закрыли крышкой). А если не равновероятны, да ещё и неизвестно какие ...

VAL
58млн это за рамками разумного. А 288 вполне. Вижу.

[Yadryara]

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

Конечно же надо: смотря как переделали,

Вот именно, что надо смотреть на то, что есть сейчас, а не на то, что было раньше. Разумеется, я имел в виду случаи, когда не имеет значения предыдущая конструкция.

Хорошо, другие примеры.

Раньше была другая рулетка, её убрали. Теперь есть эта, с 35-ю числами.
Раньше она была односкоростная, а теперь четырёхскоростная.
Раньше стояла горизонтально, а теперь имеется перепад в $1^\circ$

Раньше в PARI передавались любые числа, а теперь только те, которые не делятся на простые до 3500.
Раньше в PARI передавались только те числа, которые не делятся на простые до 3500, а теперь только те, которые не делятся на простые до 4096.

Вот я и считал вероятность для последних.

[Yadryara]

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

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

О, как! Шестикратное ускорение уже незначительно!?

По сравнению с тысячекратным — да.

Кстати, при переходе от 11 одиночных простых к 3-м, по грубой прикидке оно и должно было из 1000-кратного стать 6-7-кратным:

$$1000^{\frac3{11}}\approx 6.58$$

[Yadryara]

\begin{tabular}{|l|c|c|c|c|c|c|c|} \hline & ALL & 11+ & 11 & 12 & 13 & 14 & 15 \\ \hline \text{<7e35 11-23} & 13 & 390 & 305 & 68 & 16 & 1 & \\ \text{<7e35 КМК37-11} & 8 & 538 & 430 & 94 & 10 & 4 & \\\hline \end{tabular}

S9-21-741523
652047596968702813486589937298770841
12, 12, 12, 48, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12
valids=14, ALL

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

одна любая 14-ка на 237 миллионов попыток находиться не будет, а будет встречаться реже.

Ну вот нашёл всё-таки первую 14-ку в жизни. После 466 миллионов попыток в подклассе 11-23. Сравните с везением для подкласса КМК37-11, когда для первой 14-ки хватило всего лишь 74 миллионов попыток.

Пока предполагаю, что вероятности для этих двух подклассов именно в попытках одинаковые. Только для 11-23 этих попыток делается на 27% меньше. И примерно на столько же меньше находится 11-к, 12-к и цепочек 11+.

[Dmitriy40]

По M36n13.
Пока вчера сделал паттерны (с пятой попытки, то в квадраты возвести забыл, то зеркальность неправильно учёл, то ещё что), пока определил лучшие параметры компиляции, пока они все накомпилились, стал подбирать оптимальные параметры в PARI программе перебора, запустил на ночь. Сегодня же столкнулся с двумя проблемами: явное различие в скорости выполнения в разных потоках (десятки процентов) и когда оно достаточно усреднится не очень понятно; версия x32 SSE почему-то выдаёт другие значения на выход.
С первой разбирался сегодня всё утро и день, до конца это убрать видимо невозможно, но есть надежда что на больших интервалах счёта (дни) всё нивелируется, на получасе различия не убираются никак. Пришлось ограничиться частичной факторизацией цепочек, если за секунду число не разложилось на множители, то пропускаю. Но кандидаты в решения проверяю тщательнее (хотя по идее им как раз и секунды достаточно).
С SSE очень странно, ведь для M12 отличий нет, а тут вдруг раз и появились, ровно с тем же исходным кодом. С этим продолжаю разбираться, где-то у меня глюк.
Пока предварительно оценил ускорение, для AVX2 оно составляет чуть более ста раз, для SSE кода под двести раз, моя SSE программа медленнее всего на четверть, но сам gp32 медленнее вдвое, а он занимает 75%-85% времени.

[VAL]

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

явное различие в скорости выполнения в разных потоках (десятки процентов)

Это не обязательно Ваш глюк. Просто факторизуемые числа уже достаточно велики. Для таких чисел стандартные методы факторизации могут давать весьма большие расхождения по времени. А если бы числа на входе были порядка 100 знаков, расхождение по времени (даже для чисел, не допускающих быстрой факторизации) могло быть не на десятки процентов, а тысячекратным.

[Dmitriy40]

Так я и не говорил что это глюк, это как раз понятно, к тому же десятки процентов это уже после усреднения по миллионам попыток и 72-м паттернам и явном ограничении времени на numdiv, я лишь пытался понять нет ли среди них каких-то особенных, слишком часто дающих огромные числа в разложении, потому что "мгновенная" разница на круг (миллион попыток по четверти паттернов) могла доходить до двухкратной, 293с против 148с. Но ведь хотелось же максимально выровнять нагрузку по потокам ...