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

[Yadryara]

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

Но а дальше? 37# ведь вообще не интересно, надо полный 67#.

Вы же меня ещё летом убеждали, что Вам удобен именно 37#.

Дальше проверяете 2-й 37# от центра, 5-й, 10-й, сотый. Симметрия-то никуда не девается. И в каждом 37# всего 4% (а не 6%) будут оставаться на доп. проверку.

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

1. Блоками по 32 числа из таблицы внутри интервала 37# производится отсев по простым 41-128.

Вот эту проверку надо делать пока 41-67. Возможно, фиксировать эти 377 тысяч и/или дальше проверять.

[Dmitriy40]

Хорошо, хочу посчитать возможный выигрыш.
Сейчас цикл по 41,43,47 организован снаружи (для получения выигрыша скорости), программа перебирает к примеру полный 61#=1.173e23 (чтобы время работы было разумным, это отдельный тонкий вопрос) по таблице 37# и проверяет делимости на простые 53-256 за 7.5 тактов на число, при этом первые итерации (проверки на 53-128) идут по 11 тактов на итерацию (по 32 числа). Блок из 32 числе соответственно проверяется за 240 тактов, а два таких блока (выше 61#/2 и ниже) за 480 тактов. Вы предлагаете сэкономить три итерации 53,59,61 для второй половины и воспользоваться данными от первой половины, ок. Экономия 3*11=33 тактов. Из общих 480. Это всего 7% экономии.
Прикину и без ускорения по 41,43,47 и на полный 67#. Тут скорость чуть выше (первый отсев чаще не доходит до конца), по 6.5 тактов на число или 416 тактов на 64 числа, экономим итерации 41,43,47,53,59,61,67, это 7*11=77 тактов, из 416, это 19%. Тоже не слишком много. И уж точно меньше даже выигрыша 41/24=1.7 раза от внешнего перебора по 41.
Все цифры взял реальные, из работающей программы.
Простите, но ради 7% заморачиваться не буду.
А вот если получится где-то сэкономить размер таблиц вдвое, да без потери скорости - это да, подумаю как использовать.

PS. Отдельный интересный вопрос почему в работающей программе аж 11 тактов на итерацию (по 32 числам), а в новой укладывается в 5.3 такта, хотя код фактически не различается. Возможно в работающей программе таблицы не оптимально ложатся в кэш ... Либо я где-то ошибаюсь с расчётом скорости ...

[Yadryara]

Понятно, что совет идти от $\frac{67\#}2\approx 39e23$ не очень привлекателен практически. Как понимаю, сейчас у Вас счёт идёт где-то на высоте 10-12е23. А вдруг 19-ка и в самом деле найдётся ещё до 20е23 и тогда по барабану, что там творится вблизи 39е23.

Поскольку принцип симметрии универсален, его ведь можно применить и для меньших диапазонов, например $\frac{61\#}2\approx 6e22$
Ну вот можно пойти от $10,5\cdot61\# = 1231528004273773195324335$
Фильтрация по сравнению с 67# ухудшится, но всё равно будет отбрасываться не 96%, так 94% всех кандидатов по простым модулям 41-61.

Или ещё ниже спуститься, даже до $47\#\approx 6e17$.

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

4. Если проверили все блоки по 32 в таблице 37#, то продвигаем начало интервала на величину 37# и повторяем с п.1 пока не достигнем конца заказанного интервала (он обычно 1e17 если без оптимизаций, это секунд 40 в 4 потока,

Здесь уже, как я понял можно и в один поток очень быстро управиться с проверкой по простым 41-47 и сравнить время работы, проверяя одну половину интервала 47# обычным способом, а другую — ускоренным. Главное не забывать, что магия симметрии разрушится, если проверка превысит характерное число, в данном случае 47.

[Yadryara]

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

Прикину и без ускорения по 41,43,47 и на полный 67#. Тут скорость чуть выше (первый отсев чаще не доходит до конца), по 6.5 тактов на число или 416 тактов на 64 числа, экономим итерации 41,43,47,53,59,61,67, это 7*11=77 тактов, из 416, это 19%. Тоже не слишком много.

Слишком много или не слишком, тут важен сам факт. Что человек, который заинтересовался кортежами сравнительно недавно, смог предложить рабочую идею ускорения чрезвычайно быстрой программы, которая, как понимаю, совершенствовалась годами. Ведь, грубо говоря, ничегошеньки я не понимаю в этих тактах.

И пусть, не 19%, пусть даже 7%, мне всё равно это приятно осознавать. Спасибо, что проверили мои идеи. Хотя, как понимаю, идеи проверены ещё не все.

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

Сейчас цикл по 41,43,47 организован снаружи (для получения выигрыша скорости),

Но раньше-то Вы об этом не говорили. Можно этот момент подробнее осветить?

[Dmitriy40]

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

Слишком много или не слишком, тут важен сам факт. Что человек, который заинтересовался кортежами сравнительно недавно, смог предложить рабочую идею ускорения чрезвычайно быстрой программы, которая, как понимаю, совершенствовалась годами. Ведь, грубо говоря, ничегошеньки я не понимаю в этих тактах.

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

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

Но раньше-то Вы об этом не говорили. Можно этот момент подробнее осветить?

Да там и так запутанно, о некоторых деталях умолчал (но упомянул что их пропустил): и многопоточность (ещё цикл в п.4), и оптимизация трафика памяти (ещё цикл, причём работающий между п.1 и п.4, блоки по 32 числа перебираются сначала этим циклом с шагом 37# или 47# несколько раз (фиксированное количество, не по всему заказанному диапазону), а уж потом продвигаются внутри таблицы 37#), ну и вынос части перебора наружу. Поясню конечно.

Так как моя программа стоит таблицу сама из переданного паттерна, то ещё в марте 2021 пришла идея вынести часть переборов наружу и передавать ей что по некоторым простым не надо анализировать остатки, а брать только один прямо указанный - это автоматически построит таблицу только с ним и без увеличения размера таблицы она будет покрывать больший диапазон чисел. Понятно что на одном простом не остановился и сделал передачу до 9 остатков по простым 41-71. Тогда же сделал очередной "подход к снаряду" 19-252, запустил счёт по новому, только не из PARI, а из командной строки (файла cmd) с записью в файлы и допроверкой в PARI. Считалось неделю, просчиталось 21% диапазона 0-1e22, 3374 файла в основном вообще без кандидатов, редко 1-2, лишь в 4 из них по 3 кандидата. Посмотрел я на это дело тогда и бросил. Как-то слишком геморно показалось, да и десятки тысяч файлов раздражали. Ещё и оценка времени улетала в годы. И возможно в программе ещё и глюк сидел. В общем посмотрел и бросил. А вызов программы из PARI без сохранения в файлы тогда ещё видимо не умел.
Вот пример запуска программы с передачей трёх остатков:

n=19, max=252, x: 0 6 12 30 42 72 90 96 120 126 132 156 162 180 210 222 240 246 252
3:1,2, n=2, d=2 / 6
5:1,2, n=2, d=4 / 30
7:3,4, n=2, d=8 / 210
11:4,8, n=2, d=16 / 2310
13:3,5, n=2, d=32 / 30.03e3
17:1,2, n=2, d=64 / 510.5e3
19:2,3,11,12,16,17, n=6, d=384 / 9.700e6
23:3,9,10,14,15,21, n=6, d=2304 / 223.1e6
29:1,2,3,4,5,6,7,8,11,14,24,27, n=12, d=27.65e3 / 6.470e9
31:5,9,10,11,12,13,14,15,16,17,18,22, n=12, d=331.8e3 / 200.6e9
37:1,3,4,6,8,9,10,11,14,17,18,20,24,26,27,30,33,34,35,36, n=20, d=6.636e6 / 7.421e12
41:1, n=1, d=6.636e6 / 304.3e12
43:2, n=1, d=6.636e6 / 13.08e15
47:3, n=1, d=6.636e6 / 614.9e15
53:1,4,5,6,7,8,9,12,14,15,17,18,20,21,22,24,26,28,29,30,31,35,36,37,38,40,42,44,45,46,48,49,51,52, n=34, d=225.6e6 / 32.59e18
59:1,2,3,4,5,6,7,8,9,10,11,12,13,16,18,19,20,23,24,25,27,30,31,32,33,34,35,36,37,38,39,40,41,42,44,48,50,52,54,58, n=40, d=9.024e9 / 1.923e21
61:1,5,6,7,8,9,10,11,12,13,14,15,16,17,18,20,23,24,25,28,29,30,33,35,36,37,38,39,40,41,42,43,44,45,46,47,48,52,54,56,58,60, n=42, d=379.0e9 / 117.3e21
Size:6.636e6*(16(53..127)+23(128..256))=365MB, 0.043s, d=614.9e15, k[]:0.466s, kk[]:1.034s

Как видно вместо таблицы 37# будет использоваться таблица 47#, но с тремя фиксированными остатками по 41,43,47 и потому той же длины, а делимости будут проверяться лишь по 53-.
Соответственно перебор допустимых остатков по простым 41,43,47 возлагался на внешнюю программу (любую), т.е. эту программу нужно было вызвать 24*24*28=16128 раз с разными передаваемыми остатками для каждого диапазона.
0.043с потрачено на таблицу допустимых остатков (по простым примерно до 1000) и выбор размера таблицы (в зависимости от переданного паттерна), к 0.47с вычислена КТО для 6.636e6 чисел, а к 1c вычислены и все остатки по простым 53-256 для всех 6.636e6 чисел (всё в 4 потока).

И вот тут возникает тот хитрый момент о котором говорил выше, даже два.
Так как в программе есть некие подготовительные действия (построение таблиц), то сколько-то времени тратится на них и потому чтобы не слишком замедлять общую работу надо чтобы основной счёт занимал времени раз в 10 больше инициализации, а она занимает около секунды, значит счёт должен занимать секунд 10. Это ограничивает диапазон снизу до 1e21, которые перебираются секунд за 9. Делать диапазон ещё меньше уже невыгодно, замедление от наличия инициализации будет больше 10%. Но 9с на вызов, которых надо 16128, это 40ч на 1e21. И при любом глюке можно потерять всё насчитанное в диапазоне за 40ч. Неприятно. Потому пришлось сохранять лог каждые 9с, их потерять вообще не страшно, но это усложнило перезапуск после глюков, автоматический писать не стал, всё руками (найти точку останова, поправить, аккуратно указать её в двух местах в .gp программе, запустить продолжение счёта).
Второй неприятный момент: раз проверяем делимости лишь по 53-, то допустимость 32 проверяемых чисел уменьшается медленнее и доходит ниже 1 (чтобы можно было оборвать проверку) позже, заметно позже чем при проверке с 41-. А значит выполняется больше итераций на первом отсеве, а значит медленнее работает программа. Сколько я тогда бошку ломал почему скорость на число уменьшается при попытке ускорения счёта ... А она уменьшается почти вдвое, с 2e9/c до 1.25e9/c! Но в итоге выигрыш 47/28*43/24*41/24=5.1 раз от уменьшения перебора его всё равно перекрывает и внешний перебор 41,43,47 оказывается выгодным. А и по 53 скорость падает до 0.985e9/c. Но тогда вызовов нужно сделать уже полмиллиона, и каждый хотя бы на 5e22 за 10с (и 2с на 1e22 и 4с на 2e22 и 5с на 2.5e22 слишком коротки) и выигрыш от внешнего перебора по 53 падает до 23%, зато ждать перебора всего 5e22 придётся два месяца. Посчитал это уже слишком неудобным и ограничился 47 (да, вероятно потеряв в скорости около 20%).

PS. Все цифры скорости указаны для основного компа, счёт же идёт на другом более быстром (плюс немного у Демиса). Собственно и текущий "подход к снаряду" в апреле 2023 состоялся именно из-за появления другого компа, так бы на основном запускать не стал, скорость ещё в марте 2021 совсем не радовала, а так появилась надежда управиться за полгода (но не оправдалась).
PPS. Вопрос-то пояснил или вышло пустое бла-бла-бла? Повторю, я могу и на PARI всё функционально переписать, но будет ли это понятнее? Сомневаюсь. И оно уж точно будет непригодно для анализа скорости, даже близко.

[Yadryara]

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

Вопрос-то пояснил или вышло пустое бла-бла-бла?

У Вас не бывает пустого бла-бла-бла.

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

Соответственно перебор допустимых остатков по простым 41,43,47 возлагался на внешнюю программу (любую), т.е. эту программу нужно было вызвать 24*24*28=16128 раз с разными передаваемыми остатками для каждого диапазона.

А нельзя ли её вызывать вдвое реже — 8064 раза, а парные остатки получать вычитанием? Или это не будет быстрее?

Кстати, я уже привык к симметричной таблице остатков для 10-го числа. Вот начало этой красавицы:

   2:                             1
   3:                            1 2
   5:                            2 3
   7:                            3 4
  11:                      2             9
  13:                  1                     C
  17:                            8 9
  19:                  4 5       9 A       E F
  23:          2 3           9         E           K L
  29:          5     8     B C D E F G H I     L     O

[Dmitriy40]

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

А нельзя ли её вызывать вдвое реже — 8064 раза, а парные остатки получать вычитанием? Или это не будет быстрее?

Вызвать вдвое меньше видимо можно, но ведь от проверки двух половинок никуда не уйти, можно лишь не проверять во второй те что вылетели на первой по простым 53-61, т.е. вызовов вдвое меньше, зато вычислений в циклах почти вдвое больше, и экономия лишь тех самых 3 (7) итераций по простым 53-61 (41-67), что и прикинул выше, остальные то простые (а программа использует простые до 256, а дальнейшая проверка на дельфи и до 100тыс) придётся проверять в обеих половинах по 47#, по ним нас пока что интересует лишь нижняя половина соответствующего праймориала (остаётся неплохая надежда найти решение до 2-3e24, даже ниже 67#/2).
Либо я недопонимаю что тут можно сэкономить. Или даже по какому праймориалу берётся симметрия, по 47#/2 (вроде как, раз 8064 вызовов) или по 67#/2 ...

(Оффтоп)

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

У Вас не бывает пустого бла-бла-бла.

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

[Yadryara]

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

что и прикинул выше

То есть Вы только прикинули, но не запускали? А вдруг практика разойдётся с теорией.

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

Или даже по какому праймориалу берётся симметрия, по 47#/2 (вроде как, раз 8064 вызовов) или по 67#/2 ...

Ну так по любому праймориалу(до 67) можно брать симметрию и достраивать вторую половину. Если Вам не влом, может стоит протестировать и так и сяк.

Кстати, не только по праймориалу можно брать симметрию, но и по любому произведению простых. Скажем, $47\#\cdot109\cdot113\cdot127$

[Dmitriy40]

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

То есть Вы только прикинули, но не запускали? А вдруг практика разойдётся с теорией.

Конечно не запускал. Это ж ещё писать и писать. Только чтобы получить те цифры по прикидке выше понадобилось несколько часов и готовая программа из которой лишь убирал лишние части, а уж писать новое ...
Плюс я не совсем понимаю что именно можно сэкономить. Три итерации, что вроде бы понимаю? Смысла нет. Половину вызовов? Не понимаю как, не увеличивая вычислений на каждый вызов. Размер таблицы вдвое при том же количестве вызовов? Так размер таблицы не является ограничивающим фактором.
С другой стороны, практика обычно хуже теории, потому что прикидываю ведь наилучший результат, теоретически возможный, а любые накладные расходы при реализации будут его лишь ухудшать.

Я вон весь день не могу поверить что один и тот же код в одном случае занимает 11 тактов, а в другом (более искусственном) всего 5.3 такта. А всё различие - в размерах таблицы и порядке её обхода и что во втором случае таблица пустая (но скорость и не должна зависеть от содержимого таблицы). Сначала думал кэш не справляется и тормозит, прикинул, нет, даже память успевает с огромным запасом (я же специально этим озаботился ещё в 2017). Накладные расходы (на переключение задач и пересчёт остатков на новую границу 37#) тоже по идее малы. А скорость вдвое отличается. Бред какой-то. Как будто где-то ошибаюсь в арифметике ... Четырьмя разными способами пересчитываю скорости, обе по отдельности совпадают, друг с другом - вдвое различаются. Парадокс.

[Yadryara]

Пока отвлекусь на другую плохую новость по проекту SPT. Хорошо известно, что прогнозы дело неблагодарное.

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

Интересным является и рубеж $2^{63}$. Который может быть достигнут примерно через месяц-полтора.

Почти два с половиной месяца прошло. Не достигнут. И скорость упала уже впятеро: с рекордных 6.5 TF в начале декабря до нынешних 1.3 TF.

https://boinc.termit.me/adsl/server_status.php

[Yadryara]

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

Интересным является и рубеж $2^{63}$. Который может быть достигнут примерно через месяц-полтора.

Сегодня перекроют наконец-то. И, прям вплотную к рубежу найдена аж 3-я 19-ка. На этот раз с круглым диаметром 600:

9218260110780722411: 0 18 102 120 132 222 252 258 270 300 330 342 348 378 468 480 498 582 600

Начнут, в ближайшие часы уже начнут появляться решения выше 9223372е12.

[Yadryara]

Да, компы кранчеров достигли этого рубежа где-то в 12 часов по Москве. Но никаких значений из Баз Данных увидеть не удаётся уже 2-й час. И все количества кортежей застряли на одних и тех же значениях.

Странно, ведь о возможных проблемах организатором было известно задолго до рубежа. Например, впс говорил 1-го декабря:

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

Интересным является и рубеж $2^{63}$. Который может быть достигнут примерно через месяц-полтора. Инвертирование старшего бита при достижении этого рубежа может вызвать проблемы, могут появиться отрицательные числа.

Болд и шрифт добавил сейчас.

И не только я ведь предупреждал. И в ноябре шла речь об этом. Неужели всё-таки оказались не готовы... Задания пока продолжают выдаваться.

[Dmitriy40]

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

Но никаких значений из Баз Данных увидеть не удаётся уже 2-й час. И все количества кортежей застряли на одних и тех же значениях.

Демис сделал кэширование количества кортежей (и списка самых длинных), оно обновляется раз в 2-4 часа (не помню точно), так что смотреть чаще бессмысленно, оно часами может не обновляться, а потом резко скакнуть.
А вот списки цепочек не кэшируются и выдаются напрямую из БД, если нужна оперативная инфа то смотреть надо их (например удобно смотреть SPT13, их достаточно много и в то же время пока помещаются на одну страницу списка). Правда намного-намного медленнее (например SPT19 только что выдавались аж 40 минут! но обычно хватает 5-6).

Проблема была известна задолго до 1 декабря. Я даже предлагал выдать задание скажем на 1e19 и посмотреть как оно отработается, от начала (выдачи) и до конца (записи цепочек в БД и выдачи на сайт). Проблема на самом деле скорее всего лишь на сайте (в коде PHP), в БД будет всё правильно (а уж само приложение точно считает правильно, это я уже давно проверил). Но, "есть более важные дела и проблемы" ... Ведь до сих пор не сделана нормальная (или хоть какая-то рабочая) разбивка по страницам, т.е. получить полные списки длиннее 200тыс элементов практически невозможно.

[Yadryara]

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

Демис сделал кэширование количества кортежей (и списка самых длинных), оно обновляется раз в 2-4 часа (не помню точно),

А я помню точно. Стандартное время — 15 минут.

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

так что смотреть чаще бессмысленно,

Не бессмысленно.

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

например удобно смотреть SPT13

Я как раз их обычно и смотрю.

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

Правда намного-намного медленнее (например SPT19 только что выдавались аж 40 минут! но обычно хватает 5-6).

Обычно да, 5-8 минут.

Вот, спустя 30-40 минут скачались 13-ки. Наибольшая пока — 9222894е12. Подождём.

[Dmitriy40]

Всё. порог преодолён:
9223610669641118953: 0 10 48 66 108 114 126 160 174 208 220 226 268 286 324 334
На удивление ошибок не вижу.

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

А я помню точно. Стандартное время — 15 минут.

И однако количество SPT16=5623002 сохраняется уже с 14:40 (когда решил последить) по 15:07, что больше 15 минут.

-- 10.03.2024, 15:15 --

Впрочем да, может быть за всё это время реально ни одной новой SPT16 не получено и не учтено ... Попробую подловить появление новых SPT16 и сравню через сколько обновится общее количество.