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

[Yadryara]

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

Во-первых группа G5@71# закрыта не будет. Потому что она зависит от групп G5...7@67#, а не только от G5@67#.

Ну так это понятно. Группа G5@67# будет закрыта для 71#.

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

Но это в 70 раз дольше, не в 52,

Ну так я написал что необязательно 70, можно, например 13 периодов обсчитать, до 1е26. Там сколько чистых кортежей 19/19 ожидается? 3 с лишним штуки небось.

В этом и смысл. Всего в 13 раз больше, а не в 71 и не в 52.

[Dmitriy40]

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

Кстати, может это банальность, но скажу. С экранной клавы печатаю со вчерашнего дня. Не знаю, может и порт PS/2 отключился. Так вот, я неработающую клаву от компа отсоединил. И ночью был установлен рекорд скорости счёта одного юнита:

55 минут 18 секунд и до 3.96 ГГц
против старого рекорда
56 минут 20 секунд и до 3.88 ГГц

И не греется как раньше. Раньше руку подносишь к вент. отверстиям -- горяченький воздух. А сейчас едва тёплый.

Это сравнение недостаточно корректно. Сравнивать надо время вычисления одного и того же юнита. Разные юниты могут чуть по разному нагружать процессор (проверки простоты обрывать на разной глубине), что само по себе уже даёт разное время счёта, плюс из-за этого может скакать частота (так как меняется доля AVX команд и соответственно ток потребления) и ещё сильнее время счёта. Да, за 2.3e13 проверок всё может хорошо усредниться, но может и не до конца, ведь дальние проверки делаются относительно редко, не все 2.3e13 раз конечно же и потому их усреднение идёт не так эффективно.

[Yadryara]

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

Да не получается это! Так бы быстро насчитал чистую группу для 127# с чем долго мучились до HL1.

Да при чём тут 127#. Нам и 113# вполне хватило бы и я прекрасно помню что не удалось дотуда досчитать. Я ищу уже хоть какие-то возможности, хоть самые чистые для 73# или 79# посчитать. Статистику посмотреть.

Так-то мы можем ведь просто взять и с тем же разбиением на 13824 и 2-й период 67# считать. Только очень скучно.

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

Это сравнение недостаточно корректно. Сравнивать надо время вычисления одного и того же юнита.

Ну как всегда. Я уже 2-й месяц считаю. 9-ю сотню юнитов считаю. В самых лучших случаях 56 минут и 20-50 секунд. Мне трудно подробно писать, говорю же. Стоит не написать, что я сделал вывод по нескольким юнитам:

Time: 57min, 24,471 ms / 57min, 44,001 ms
2817=64874729
Time: 57min, 5,197 ms / 57min, 24,804 ms
2818=329048639
Time: 58min, 21,414 ms / 58min, 41,181 ms
2819=355294859
Time: 56min, 32,121 ms / 56min, 51,335 ms
2820=14093999
Time: 55min, 6,496 ms / 55min, 25,992 ms
2821=53463329
Time: 55min, 6,098 ms / 55min, 25,419 ms
2822=263433089
Time: 54min, 59,261 ms / 55min, 18,380 ms
2823=378688229
Time: 55min, 451 ms / 55min, 19,835 ms
2824=24364259
2824=24364259:3314425845914041136177567: [  +0,  -2,   6, +12,  30,  42,  72,  90,  96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246, 252], len=18, valids=17
Time: 54min, 58,858 ms / 55min, 18,102 ms
2825=63733589
Time: 55min, 54,605 ms / 56min, 13,955 ms
2826=313072679
Time: 57min, 46,810 ms / 58min, 6,357 ms
2827=309078689
Time: 57min, 23,715 ms / 57min, 43,098 ms

Вот же они 5 юнитов подряд посчитанные ночью без лишней нагрузки на комп. Все как один по 55 с лишним минут.

[Dmitriy40]

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

В этом и смысл. Всего в 13 раз больше, а не в 71 и не в 52.

Это возврат к линейной проверке. Пусть и только по 71. Почему я и не понимаю в чём тут выгода если можно ровно тот же интервал проверять в 71/52=1.365 раза быстрее (минус накладные расходы на пропуск остального интервала, но для достаточно больших считаемых интервалов я надеюсь сделать их малыми).
Вот сделал тест на 71#, вычисление только 1-2e26, время уменьшилось с 181с до 43.6с, всего лишь в 4.16 раза вместо 5.56 раз. Но это код пропуска лишь на 32 юнита @71#, не сразу на кусок из 20736, того ещё не писал.

С другой стороны, этот тест работает со скоростью 407e6/с юнитов @71# вместо 522e6/с юнитов @67# текущей программы. Понятно почему - хуже отфильтровываются кандидаты при проверке по простым 73-127 вместо 71-127 и потому остальные проверки запускаются в 1.365 раза чаще, а они занимают 70% общего времени.
Тогда выгоднее вообще запускать текущую программу поиска в 67#, только начинать не с 0, а с n*67#. И тогда если кортеж найдётся до n=52*407/522=41, то это будет быстрее. Да, хороший вариант. Код подправить чтобы он инициализировал таблицы не с 0 не так сложно. В интервале [0, 41*67#] ожидаем $7.361 \pm 2.713k$ кортежей, или с вероятностью в 2 сигмы (95.45%) их будет от 2 до 13 штук или с вероятностью 1% их окажется меньше 1шт. Да, выгодно.
Можно даже найти тот интервал n*67#, в котором вероятность обнаружить менее 1 кортежа составляет 50% (собственно его уже находил, это где мат.ожидание равно 1, на 2.6*67#, можно взять 3*67#) - и вот его и перебирать, весь, начиная с чистых групп. Не найдётся - переходить к следующему чуть большему (из-за падения мат.ожидания) куску.

С третьей стороны, в 67# ожидалось $7.416 \pm 2.723$ грязных кортежей с valids=19, а найдено лишь 3 и если больше не найдутся, то вероятность такого всего лишь 5.2%, однако оно реализовалось. Потому слишком уж опираться на вероятность и мат.ожидание рискованно.

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

Только очень скучно.

Да, мне тоже интереснее поковыряться с разными методами и алгоритмами и прочим (например применить в тесте простоты Ферма для 128-битных чисел, что только что написал, редукцию Монтгомери что должна дать минимум 10-кратное ускорение проверки, а может и 100-кратное, там же вообще не нужна операция взятия остатка по модулю, которая занимает 600-900 тактов при том что даже три нужных ей умножения займут около десятка тактов), но если ставить задачу найти 19-252 (а например Демис помогает решить именно её), то выгоднее считать скучно, но быстрее.

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

Вот же они 5 юнитов подряд посчитанные ночью без лишней нагрузки на комп. Все как один по 55 с лишним минут.

Мне остаётся только повторить что если хотите установить причину повышения скорости, то сравнивать надо один и тот же юнит, а не разные. Иначе сравнение в разных условиях и неизвестно что на что и как влияет. Может у вас температура в комнате упала на градус (ночью совсем не удивительно) и потому улучшился теплосъём с проца что дало ему возможность поднять частоту на 2%, вполне правдоподобно. Независимо от клавы и юнитов.
Рекорд скорости да, установлен, его причина - нет, осталась неизвестной. Я только про это.

[Dmitriy40]

А вот например для 17-240-1, которых до 59# лишь одна при ожидаемых $0.5666 \pm 0.7527k$ (с учётом загрязнения до 8-ю числами), вероятность такого (что будет $1 \le N < 2$ кортежей) составляет всего 25%. И тоже реализовалось.
Так что вполне реальны события с достаточно низкими вероятностями.
И если реализация маловероятного события "кортеж найден раньше ожидаемого" нам только лучше, то реализация маловероятного события "кортеж в интервале не найден" гораздо неприятнее. И хотелось бы так построить работу, чтобы даже для относительно маловероятных событий не пришлось считать в разы больше самого наискучнейшего поиска (за который считать перебор всего 71# в произвольном порядке, как начинал 4 августа).

[Dmitriy40]

Решил посчитать и выложить (надоело каждый раз заново пересчитывать) табличку вероятностей (по методу стандартного отклонения для случая полной проверки соответствующего интервала) отсутствия кортежей на заданном интервале грануляцией 67# с нуля и вероятность наличия кортежей в каждом длиной 67# (уже не с нуля кроме первого):
\begin{tabular}{|c|ccc|ccc|} \hline \times 67\# & \mu & \sigma & P(X < 1) & \mu & \sigma & P(X \ge 1) \\ \hline 1 & 0.5112 & 0.7150 & 75.3\% & 0.5112 & 0.7150 & 24.7\% \\ 2 & 0.8374 & 0.9151 & 57.0\% & 0.3262 & 0.5712 & 11.9\% \\ 3 & 1.119 & 1.058 & 45.5\% & 0.2814 & 0.5304 & 8.77\% \\ 4 & 1.375 & 1.172 & 37.5\% & 0.2558 & 0.5058 & 7.06\% \\ 5 & 1.613 & 1.270 & 31.5\% & 0.2384 & 0.4883 & 5.94\% \\ 6 & 1.839 & 1.356 & 26.8\% & 0.2255 & 0.4749 & 5.14\% \\ 7 & 2.054 & 1.433 & 23.1\% & 0.2153 & 0.4640 & 4.54\% \\ 8 & 2.261 & 1.504 & 20.1\% & 0.2069 & 0.4549 & 4.06\% \\ 9 & 2.461 & 1.569 & 17.6\% & 0.1999 & 0.4471 & 3.68\% \\ 10 & 2.655 & 1.629 & 15.5\% & 0.1939 & 0.4403 & 3.36\% \\ 11 & 2.843 & 1.686 & 13.7\% & 0.1886 & 0.4343 & 3.09\% \\ 12 & 3.027 & 1.740 & 12.2\% & 0.1840 & 0.4289 & 2.86\% \\ 13 & 3.207 & 1.791 & 10.9\% & 0.1798 & 0.4241 & 2.65\% \\ 14 & 3.383 & 1.839 & 9.76\% & 0.1761 & 0.4196 & 2.48\% \\ 15 & 3.556 & 1.886 & 8.77\% & 0.1727 & 0.4155 & 2.32\% \\ 16 & 3.725 & 1.930 & 7.90\% & 0.1696 & 0.4118 & 2.19\% \\ 17 & 3.892 & 1.973 & 7.13\% & 0.1667 & 0.4083 & 2.06\% \\ 18 & 4.056 & 2.014 & 6.46\% & 0.1640 & 0.4050 & 1.95\% \\ 19 & 4.218 & 2.054 & 5.86\% & 0.1616 & 0.4020 & 1.85\% \\ 20 & 4.377 & 2.092 & 5.33\% & 0.1593 & 0.3991 & 1.76\% \\ 21 & 4.534 & 2.129 & 4.85\% & 0.1571 & 0.3964 & 1.67\% \\ 22 & 4.689 & 2.165 & 4.42\% & 0.1551 & 0.3938 & 1.60\% \\ 23 & 4.842 & 2.201 & 4.04\% & 0.1532 & 0.3914 & 1.53\% \\ 24 & 4.994 & 2.235 & 3.70\% & 0.1514 & 0.3891 & 1.46\% \\ 25 & 5.143 & 2.268 & 3.39\% & 0.1497 & 0.3869 & 1.40\% \\ 26 & 5.292 & 2.300 & 3.10\% & 0.1481 & 0.3848 & 1.34\% \\ 27 & 5.438 & 2.332 & 2.85\% & 0.1466 & 0.3828 & 1.29\% \\ 28 & 5.583 & 2.363 & 2.62\% & 0.1451 & 0.3809 & 1.24\% \\ 29 & 5.727 & 2.393 & 2.41\% & 0.1437 & 0.3791 & 1.19\% \\ 30 & 5.869 & 2.423 & 2.22\% & 0.1424 & 0.3773 & 1.15\% \\ 31 & 6.010 & 2.452 & 2.05\% & 0.1411 & 0.3756 & 1.11\% \\ 32 & 6.150 & 2.480 & 1.89\% & 0.1399 & 0.3740 & 1.07\% \\ 33 & 6.289 & 2.508 & 1.75\% & 0.1387 & 0.3724 & 1.04\% \\ 34 & 6.426 & 2.535 & 1.62\% & 0.1376 & 0.3709 & 1.00\% \\ 35 & 6.563 & 2.562 & 1.49\% & 0.1365 & 0.3694 & 0.970\% \\ 36 & 6.698 & 2.588 & 1.38\% & 0.1354 & 0.3680 & 0.940\% \\ 37 & 6.833 & 2.614 & 1.28\% & 0.1344 & 0.3666 & 0.911\% \\ 38 & 6.966 & 2.639 & 1.19\% & 0.1334 & 0.3653 & 0.884\% \\ 39 & 7.099 & 2.664 & 1.10\% & 0.1325 & 0.3640 & 0.858\% \\ 40 & 7.230 & 2.689 & 1.03\% & 0.1316 & 0.3627 & 0.833\% \\ 41 & 7.361 & 2.713 & 0.953\% & 0.1307 & 0.3615 & 0.809\% \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ 52 & 8.747 & 2.958 & 0.440\% & 0.1225 & 0.3500 & 0.609\% \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ 71=71\# & 10.970 & 3.312 & 0.131\% & 0.1126 & 0.3356 & 0.410\% \\ \hline \end{tabular}
Пропущенные уже не так интересны.
Судя по ней считать придётся раз в 5-8-13-20 больше одного 67#, смотря какая вероятность реализуется.

[Dmitriy40]

Yadryara, DemISdx
По поводу ошибок вычислений, вот только что проверка целостности обнаружила что 6 пар файлов в начале моего считаемого 12ххх (в первых 50 файлах, сейчас считается 340-й) некорректна. Первый файл в паре обрезан в конце, во втором вообще какая-то чушь, совсем без текста. Причём размеры всех файлов похожи на правильные, некорректно только содержимое. Скорее всего вычисления были правильными, а ошибка произошла при записи на носитель (в винде сбилась что-то типа $MFT). Но корректных данных не осталось, придётся пересчитывать, это на 6ч работы.
Возможно это связано с записью на USB флешку (вычислительный сервер грузится с неё и туда же пишет результаты), не знаю. На данную флешку всего писалось несколько десятков тысяч файлов и проблема обнаружилась вот только сейчас. В те моменты перезапусков сервера точно не было.
Я это к тому что ошибки всё же возможны. Даже если их годами не видеть, однажды они могут возникнуть. Тем более при таких массовых вычислениях (месяцы и годы). И надо быть готовым к их обнаружению и исправлению.

-- 17.11.2024, 02:02 --

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

А вот например для 17-240-1, которых до 59# лишь одна при ожидаемых $0.5666 \pm 0.7527k$ (с учётом загрязнения до 8-ю числами), вероятность такого (что будет $1 \le N < 2$ кортежей) составляет всего 25%. И тоже реализовалось.

Уточнение по загрязнениям до 10 простыми: $59\#: X=0.4922 \pm 0.7015k, P(1 \le X < 2)=22\%$, однако реализовалась.

[Yadryara]

Здорово. Я сам хотел сделать, но поленился. Правда, хотел посчитать только матожидания. Ну да, как и предполагал ожидается больше 3 штук 19/19 для 13 периодов.

Вы вручную что ли данные переносили? Уже для 2-го периода ошибку заметил: не 0.8274, а 0.8374.

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

Судя по ней считать придётся раз в 5-8-13-20 больше одного 67#

Тогда уж 1-20 периодов по 67# каждый.

[Dmitriy40]

Первые пару строку вручную (пока с таблицей разбирался), потом надоело и поправил программу для вывода в нужном формате, тем более что $P()$ для первых двух строк (при $\mu<1$) считается чуть по другому.
Спасибо, поправил.

[Yadryara]

4-й столбец лучше поменять и тоже указывать там $P(X \geqslant 1)$.

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

[DemISdx]

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

Yadryara, DemISdx
По поводу ошибок вычислений, вот только что проверка целостности обнаружила что 6 пар файлов в начале моего считаемого 12ххх (в первых 50 файлах, сейчас считается 340-й) некорректна. Первый файл в паре обрезан в конце, во втором вообще какая-то чушь, совсем без текста. Причём размеры всех файлов похожи на правильные, некорректно только содержимое. Скорее всего вычисления были правильными, а ошибка произошла при записи на носитель (в винде сбилась что-то типа $MFT). Но корректных данных не осталось, придётся пересчитывать, это на 6ч работы.
Возможно это связано с записью на USB флешку (вычислительный сервер грузится с неё и туда же пишет результаты), не знаю. На данную флешку всего писалось несколько десятков тысяч файлов и проблема обнаружилась вот только сейчас. В те моменты перезапусков сервера точно не было.
Я это к тому что ошибки всё же возможны. Даже если их годами не видеть, однажды они могут возникнуть. Тем более при таких массовых вычислениях (месяцы и годы). И надо быть готовым к их обнаружению и исправлению.

Жаль конечно. Мне казалось, что не однократно о таком поведении на usb писал.

(Оффтоп)

Когда-то видел как бъются например jpeg файлы при перекачке на комп. Второй раз копируешь - нормально. Полез даже когда-то разбираться почему такое может происходить. Уперся в то, что сам юсб (по крайней мере 1.2, 2.0, про 3.0 не знаю) имеет только примерно 95% доставку (подзабыл уже, но в тексте было написано негарантированной доставки). И это зашито в самом интерфейсе. На системах где загружаюсь с юсб частенько наблюдаю сбои.
Но на второй третий раз прокатывает.
Редко когда это зависит от производителя флешки, но тоже бывают фокусы и от них.
Юникс, линукс - сразу сыпят ошибками при загрузке.
Винда - только в режиме отладки (но кто-же ее ставит в режиме отладки при загрузке с юсб??? :) )

[Dmitriy40]

71# будем считать по разбиению
43#/23...37: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 120, 1132, 5390, 17178, 35090, 52468, 52224, 35478, 16638, 4820, 642], sum=221184
кусками по 67# начиная с более чистых в каждом куске.
Судя по таблице выше, достаточно будет нескольких первых кусков, что выгоднее 1/11 перебора всего 71# в случайном порядке, особенно если кортежей там меньше 11, но не меньше 1.5.
221 тысяч файлов лога неразумно, потому они объединяются в пределах группы по 100шт в один. И раскидываются по папкам по кускам и группам. По полтысячи файлов в папке нормально.
Для сокращения размеров логов цепочки с valids<15 выводить в лог не буду, они не интересны. Цепочки valids>14 попадаются не в каждом юните, так что 50%-80% юнитов будут пустыми. Ну и ладно.
Перебор идёт по указанным диапазонам в куске и группе, вплоть до одного юнита. Но удобнее минимум по 100, чтобы попадали в один файл лога.
При перезапуске по любым причинам счёт автоматически продолжается после последнего корректно посчитанного юнита (это ещё доделываю), никаких действий не требуется при условии сохранения хотя бы двух самых новых файлов лога.

Ориентировочное время счёта одного юнита: 80с у Демиса, 2м у меня, 3.6м у Антона. В сутки: 1000 юнитов (и 10 файлов логов) у Демиса на комп, 720/850 юнитов (и 7/8 файлов) у меня, 400 юнитов (4 файла) у Антона. Тоже нормально.
Распределить юниты между нами предлагаю так:
группы G19,G20,G21, 800 из G22 Антону, 4+120+1132+800=2056 юнита, на 5 дней;
4590 из G22 мне, 4590 юнита, на 5.4 дней;
по 4000 из G23 Демису на комп, на 4 дня.
Дальше Демису по 5000 на комп, нам остатки в группах пропорционально (кратно 100 в группе).
Последние группы разберём позже, смотря кто сколько сможет и захочет считать.

[Yadryara]

Да, это здоровское разбиение.

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

Последние группы разберём позже,

Вот ещё и непонятно: то ли вообще сколько-то самых грязных групп не считать пока и переходить к следующему 67# пораньше... Но это пока неактуально, позже можно будет посчитать.

[Dmitriy40]

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

Вот ещё и непонятно: то ли вообще сколько-то самых грязных групп не считать пока и переходить к следующему 67# пораньше...

Думал. По идее как только осталось меньше юнитов в процентах чем отношение мат.ожиданий между кусками, можно переходить к следующему куску и считать уже его. Вплоть до пока отношение мат.ожиданий снова не перевернётся и тогда вернуться к верхнему куску. И так далее. Фактически счёт пойдёт по левому верхнему углу треугольником, несколько шагов вправо, шаг вправо ниже уровнем (в следующем куске), и иногда снова ниже уровнем, и ещё более иногда ещё ниже, на каждом следующем уровне (куске) посчитано будет меньше и меньше юнитов. Но это блин морока ... Ради не слишком большого сугубо теоретического (статистику по группам мы нормально посчитать не можем, это не HL1) выигрыша.

К тому же я сильно подозреваю что практически все кортежи будут в самых больших средних группах. Просто из-за их объёма. Как все три грязных 19 в 0 куске 67#, они в группах G25, G26, G27 разбиения
29#/17: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 68, 278, 800, 1896, 3140, 3578, 2400, 1208, 352, 78, 20, 2], sum=13824
размерами соответственно 1896, 3140, 3578, практически самые большие из всех (в G28=9765...12164 цепочки ещё могут и должны бы найтись, 3шт маловато).
А тогда практически нет смысла переходить к следующему куску после 1-2 из 4-х самых больших групп. А после 3-х поздно , проще и 4-ю досчитать. А где 4 самых больших группы на 79%, там и все 100% недалеко, тоже мало смысла морочиться.

[Yadryara]

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

G28=9765...12164 цепочки ещё могут и должны бы найтись, 3шт маловато).

Тут же ещё одна задача как была так и остаётся: не просто найти 19-252, а найти минимальную. Скучно, но придётся считать все группы.

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

Как все три грязных 19 в 0 куске 67#, они в группах G25, G26, G27

И самая грязная 19\22 как раз в самой грязной группе G27. Что неудивительно.

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

в G28=9765...12164 цепочки ещё могут и должны бы найтись, 3шт маловато

Не для Вас всё же проговорю довольно очевидную вещь. Для миллионов HL1 весьма хороша. Вот если ожидаем 7.40 млн кортежей, то найдутся 7.39-7.41 млн. А если ожидаем 7.4 штуки, то найдутся 0-15 кортежей. Это если кто-то не понимает, что надёжности от прогноза по единичным кортежам ждать необязательно.