Пентадекатлон мечты : Компьютерные сети и Web-технологии - Страница 112 fixfix
2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 109, 110, 111, 112, 113, 114, 115 ... 215  След.
 
 Re: Пентадекатлон мечты
Сообщение14.08.2022, 14:37 
Аватара пользователя


29/04/13
8356
Богородский
Dmitriy40 в сообщении #1562699 писал(а):
Соответственно ускоритель будет проверять следующие числа начала цепочек: $106022957662445288229350041 + 440538835723387181869888800 \cdot (2 + 6 i)$, $i \ge 0$. И для $i=1$ (вторая проверяемая ускорителем цепочка) второе число в цепочке после деления на $722$ даст ровно $p1$. Вуаля.

Это трижды хорошо.

И то, что реальный шаг здесь всё-таки 6-кратный.

И то, что ошибка найдена и понятно в чём она состоит.

И то, что эта ошибка в проге VAL(даже если она дублируется во многих прогах, пусть даже во всех) не ставит под сомнение полученные по этим прогам результаты. Ибо задачи минимизации, насколько я знаю, ни разу с их помощью не решались.

Dmitriy40 в сообщении #1562706 писал(а):
В общем их много, 7765 из 46080 для исходного комплекта.

Для других комплектов и сами паттерны другие, и их количество немного отличается (например 7672 вместо 7765).

То есть болле 7 тысяч раз для того или иного комплекта проверка по стартовой точке передаётся в Пари. А дальше что происходит? Если смягчить условия(в большом ифе), какие-то цепочки найдутся?

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение14.08.2022, 15:55 
Заслуженный участник


20/08/14
11886
Россия, Москва
Yadryara в сообщении #1562709 писал(а):
И то, что реальный шаг здесь всё-таки 6-кратный.
Я всё же предпочитаю использовать термин шаг в применении к pp=Mod(), потому что именно этот шаг виден в программах на PARI работающих с ускорителями.
А какой он реально внутри ускорителей - дело десятое.
Например в 310-м комплекте при bb=[5,37] как собственно Вы использовали шаг проверки индексов очевидно был Blocks=1110/104=10.673x - не 6х, а в среднем 10.673х.
В 1744 комплекте я выставил bb=[17,41] и шаг проверки индексов получился Blocks=4182/180=23.233x, уже ну совсем не 6х.
В 482 комплекте я не пожадничал памяти (что впрочем несколько затормозило счёт) и выставил bb=[5,17,43], что дало шаг проверки индексов уже Blocks=21930/768=28.555x.
И это увеличение шага проверки индексов обрабатывается на этапе компиляции, потом ускоритель на это времени уже не тратит (как и программа VAL не тратит времени на ушестерение шага).
Так что нет, реальный шаг в ускорителях обычно вовсе не шестикратный, а больше, иногда в разы, даже в среднем, а уж между каждыми соседними допустимыми индексами разница может и ещё больше быть (если окажутся недопустимыми несколько индексов подряд).
Но это проблемы личное дело ускорителя, какой у него шаг проверки индексов, переборная PARI программа счёта от этого никак не зависит, она всегда спокойно работает в терминах pp=Mod(). И я не вижу никакой вменяемой причины наводить путаницу с увеличением шага, которое только внутри ускорителей и которое зависит от параметров компиляции ускорителей даже для одних и тех же паттернов. Полезно отделять математику (шаг в pp=Mod()) от варианта конкретной реализации (варианты bb[]). При этом в математике не надо помнить во сколько раз надо увеличить шаг для каждого класса паттернов (это только для M12 можно 6х, для многих других нельзя, только 2х).
Yadryara в сообщении #1562709 писал(а):
То есть болле 7 тысяч раз для того или иного комплекта проверка по стартовой точке передаётся в Пари. А дальше что происходит? Если смягчить условия(в большом ифе), какие-то цепочки найдутся?
А дальше каждый ускоритель проверяет такой индекс на допустимость по остальным простым до выбранного порога (4096) и если нулевой остаток для всех них допустим (это эквивалентно что числа цепочки не делятся на данные простые), то такой индекс (нулевой) вернётся в PARI как результат работы ускорителя и PARI допроверит цепочку. Разумеется индекс вернётся не моментально по нахождению, а лишь по окончанию проверки всего заказанного ускорителю интервала индексов, а всё найденное вернётся в PARI в виде списка (массива, вектора) индексов (в vi[]).
Если по какому то простому нулевой остаток для индекса недопустим, значит какое-то число в цепочке (может и не одно) делится на соответствующее простое и соответственно оно уже не большое простое, т.е. данный индекс цепочки не подходит и в PARI не вернётся, а ускоритель перейдёт к проверке следующего допустимого индекса.

-- 14.08.2022, 16:17 --

Yadryara
По большому счёту для ускорителей вообще нет понятия шаг проверки индексов. Есть список допустимых индексов (по модулю блока), посмотреть можно в таблице по метке offsets в файле .inc, вот они и проверяются. А уж с каким они идут шагом, постоянным, переменным или ещё каким - фиолетово.
Но можно ввести (и я именно так и пользуюсь везде выше) понятие среднего шага - просто как отношение общего количества индексов в блоке (произведение простых из bb[]) к количеству проверяемых индексов в блоке. Именно это число и показывается при компиляции в строке Blocks=4182/180=23.233x. Это понятие удобно для оценки скорости работы, но никак не порядка проверки.
Да, можно заставить ускоритель использовать фиксированный шаг проверки (оставить bb[] пустым или вписать туда только те простые, по которым допустимы абсолютно все остатки - а такого не бывает), но это обычно приводит к тому что допустимым оказывается лишь один индекс, что резко тормозит ускоритель и потому не применяется. Хотите попробуйте. Я где-то выше в советах о выборе параметров bb[] говорил - очень желательно чтобы количество допустимых индексов (число в знаменателе в Blocks=4182/180) было порядка сотни и более, иначе начнутся тормоза в работе ускорителей.
Понятие блока нужно для ускорения работы ускорителя, (сорри), чтобы пореже выполнять очень длительные действия (перерасчёт текущих остатков по модулю всех простых до указанного порога для всех 11-ти проверяемых чисел, это порядка 3000 остатков!), не на каждый допустимый индекс, а лишь один раз на блок. Во внешней переборной PARI программе счёта понятия блок индексов не используется, там математика, а не тонкости оптимизации вычислений в ускорителях.

-- 14.08.2022, 16:36 --

Yadryara
Если Вам так интересно возвращаются ли в PARI нулевые индексы, запустите в консоли в корневой папке любого комплекта ускорителей команду типа for /f %f in ('dir /a-d /s /b *.exe') do @%f 0 6 и посмотрите на результат, если что-то найдётся, то массив/вектор окажется не пустым. У меня одна группа из 720 ускорителей x32 SSE какого-то комплекта отработала эту команду за 21с. В принципе эти 30мс можно считать накладными расходами на вызов ускорителя.
Для исходного комплекта все 46080 x32 SSE ускорителей выдали два варианта: 3 и 5. Нулевого не выдали.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение14.08.2022, 16:48 
Аватара пользователя


29/04/13
8356
Богородский
Dmitriy40 в сообщении #1562711 писал(а):
Так что нет, реальный шаг в ускорителях обычно вовсе не шестикратный, а больше, иногда в разы,

Ну так это отлично. Меньше 6-кратного(для 12-ти делителей) он быть не может?

Ведь это самое главное здесь. А формулировку я с удовольствием поменяю: "реальный шаг не менее чем шестикратный". По отношению к записанному в pp=Mod(). Или опять не так?

Dmitriy40 в сообщении #1562645 писал(а):
Если не ошибся, то существуют вот такие паттерны с заменой 37 на p37 с начальным числом менее 5.4e36:
v=[45,253517044545040322,169,12,49,50,1587,32,121,18,4805,28,2523,578,361]; pp=Mod(881350997235128829523053869900928345,

Вот их(все подряд) и надо попробовать крутануть дальше. То есть мой вопрос

Yadryara в сообщении #1562698 писал(а):
Было ли хоть раз такое, что начальная точка была одновременно и первой проверяемой ??

надо относить к этим числам, с большущими z(p)37.

Затем выяснить, какие из них доберутся до проверки-4096.

Затем выяснить, какие из них доберутся до проверки в Пари.

Может и не будет ни одной стартовой цепочки, которая столько препятствий преодолеет.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение14.08.2022, 18:45 
Заслуженный участник


20/08/14
11886
Россия, Москва
Yadryara в сообщении #1562713 писал(а):
Меньше 6-кратного(для 12-ти делителей) он быть не может?
Для проверяемых классов - не может. Что будет если сменить например $3^2$ на $3^5$ не знаю, не проверял (или не помню).
Yadryara в сообщении #1562713 писал(а):
А формулировку я с удовольствием поменяю: "реальный шаг не менее чем шестикратный". По отношению к записанному в pp=Mod(). Или опять не так?
Так. Пока речь про конкретные классы паттернов.
Хотя так и не понимаю этой страсти к реальному шагу ... Работает ускоритель и ладно, а какой там у него внутри шаг - ну какая разница то, может он вообще без шагов проверяет, сразу все заказанные индексы одновременно (скажем для CUDA вовсе не фантастика).
Yadryara в сообщении #1562713 писал(а):
Может и не будет ни одной стартовой цепочки, которая столько препятствий преодолеет.
Может и не будет. Только как проверить все возможные варианты то ... Или поискать хотя бы один контрпример (что будет, по крайней мере в PARI вернётся на допроверку) и успокоиться? Не вполне понимаю смысл этого.


Раздумывал вчера-сегодня над возможным переписыванием кода, как компилятора, так и самих ускорителей. Компиляцию ускорить очевидно можно, переписать почти весь PARI код на нормальном языке, почти наверняка можно уложиться в десятки мс, компиляция одного паттерна займёт 0.1с-0.2с (fasm в основном).
А вот как ускорить код ускорителей не представляю. Даже если вдруг объединить разные паттерны в один .exe, то всё равно его скорость линейно упадёт, там попросту практически нет общего кода для разных паттернов. Всё что можно наэкономить так это часть инициализации если всегда запускать ускоритель с нуля, но это лишь 6000 делений или жалкие 200 тысяч тактов, менее 0.1мс, вообще ни о чём. Ну и затраты на сам запуск .exe конечно. Для времени счёта каждого паттерна в десятые доли секунды как-то совсем мал выигрыш. А мороки over много.
Тут проще пойти другим путём: размещать не все простые в квадратах. Скажем если не размещать $17^2$, то шаг уменьшится в $17^2=289$ раз, количество паттернов сократится в 6 раз, общее время выполнения вырастет в $289/6=48$ раз. Если не размещать $37^2$, то замедление в $37^2/6=228$ раз. Правда при этом возможно будет меняться и количество проверяемых чисел (11 или 10), а следовательно и чуточку скорость ускорителей. Несмотря на такое огромное замедление для достаточно малых интервалов счёта (типа 0-1e34) может быть выгодным, надо проверять ...

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение14.08.2022, 19:11 
Аватара пользователя


29/04/13
8356
Богородский
Dmitriy40 в сообщении #1562723 писал(а):
Так. Пока речь про конкретные классы паттернов.
Хотя так и не понимаю этой страсти к реальному шагу ...

Ну как же не понимаете?! Это же хорошая новость! Ведь это означает что прав всё-таки я: из-за по меньшей мере 6-кратного увеличения реального шага по сравнению с номинальным, в 1-й строчке 1-й таблицы надо заменить 126 тысяч простых, а не 285 тысяч, как было по Вашей версии.

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

С этим могут помочь знаменитые теоретики: VAL, Денис, Евгений.

Может можно доказать, что среди стартовых чисел 15-шка найтись не может. Или как-то подскажут как сократить перебор.

Dmitriy40 в сообщении #1562723 писал(а):
Раздумывал вчера-сегодня над возможным переписыванием кода, как компилятора, так и самих ускорителей.

Хорошо бы.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение14.08.2022, 19:52 
Заслуженный участник


20/08/14
11886
Россия, Москва
Yadryara в сообщении #1562725 писал(а):
Ну как же не понимаете?! Это же хорошая новость! Ведь это означает что прав всё-таки я: из-за по меньшей мере 6-кратного увеличения реального шага по сравнению с номинальным, в 1-й строчке 1-й таблицы надо заменить 126 тысяч простых, а не 285 тысяч, как было по Вашей версии.
Вот так и не понимаю. И продолжаю не понимать: до 1.68млн подходят все простые в каждый из 46080 паттернов, от 1.68млн до 4.1млн простые подходят во всё меньшее и меньшее количество паттернов, вплоть до 3547 (но не до нуля!), ещё большие простые подходят в ещё меньшее количество паттернов, вплоть до единиц/десятков для простых за миллиарды. Это первое.
Второе, даже 126 тысяч комплектов проверить нереально.
Третье, 126 тысяч только в одной строке, ещё сравнимое количество во второй, в третьей, в четвёртой, в пятой, в шестой, а потом ещё и во всех комбинациях из двух, из трёх, из четырёх, пяти, шести. Тут счёт на квадриллионы. Даже если найдётся 15-ка в 1000 раз меньше 5.4e36 и счёт ускорим в тысячи раз (хотелось бы знать как!), всё равно нереально перебрать все.

Вы говорите 37 можно заменять только на 126 тысяч простых, видимо до 1.68млн. А что делать с этими паттернами:
v=[45,98,169,12,121,50,867,32,2527,18,2645,4,2523,1922,1001764351548313369]; pp=Mod(3480381030093155129643061394269795545, 322363843024315492299807230063304052288800); p37=1000881787;
v=[45,98,169,12,121,50,867,32,2527,18,2645,4,2523,1922,109250163281627044681]; pp=Mod(440976360599006832728484937807185945, 35156274459224194962295162174586008916071200); p37=10452280291;
Почему они недопустимы? В них 37 заменено на гораздо большее простое, однако по модулю 6 начальный индекс равен нулю, т.е. именно что стартовая точка и должна проверяться. Более того, первый допускает и для простых по 37 нулевой остаток, а второй для простых по 13. Так почему такие большие простые Вы считаете нельзя подставлять вместо 37?
Или что не найдётся простого за сотню миллионов, которое даст нулевой остаток по всем простым до 4096 и соответственно будет допустимой заменой для 37 в каком-то из 46080 паттернов?

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение14.08.2022, 20:22 
Аватара пользователя


29/04/13
8356
Богородский
Dmitriy40 в сообщении #1562729 писал(а):
Третье, 126 тысяч только в одной строке, ещё сравнимое количество во второй, в третьей, в четвёртой, в пятой, в шестой, а потом ещё и во всех комбинациях из двух, из трёх, из четырёх, пяти, шести. Тут счёт на квадриллионы. Даже если найдётся 15-ка в 1000 раз меньше 5.4e36 и счёт ускорим в тысячи раз (хотелось бы знать как!), всё равно нереально перебрать все.

Насчёт квадриллионов пока не вникал. Всё остальное мы знали ещё в апреле. То, что вариантов весьма немало.

Dmitriy40 в сообщении #1562729 писал(а):
А что делать с этими паттернами:

Так ведь только что сказал:

Yadryara в сообщении #1562725 писал(а):
Плохая новость заключается в том, что для доказательства минимальности ещё обязательно нужно проверить все стартовые числа.

Например, стартовое число

$106022957662445288229350041 + 440538835723387181869888800 \cdot (2 + 6\cdot0)$ в Ваших обозначениях и $p1-m$ в обозначениях VAL сам же VAL и не проверял. По невнимательности? Или же были какие-то причины считать, что эта проверка не нужна? Ждём ответа.

Dmitriy40 в сообщении #1562729 писал(а):
от 1.68млн до 4.1млн простые подходят во всё меньшее и меньшее количество паттернов, вплоть до 3547 (но не до нуля!), ещё большие простые подходят в ещё меньшее количество паттернов, вплоть до единиц/десятков для простых за миллиарды.

Для чисел от 1.68млн нужно проверять именно те самые стартовые числа, не более чем по одному на каждый паттерн. Стартовыми называю те, которые меньше именно 6-кратного шага, а не номинального.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение14.08.2022, 21:02 
Заслуженный участник


20/08/14
11886
Россия, Москва
Yadryara в сообщении #1562733 писал(а):
Для чисел от 1.68млн нужно проверять именно те самые стартовые числа, не более чем по одному на каждый паттерн. Стартовыми называю те, которые меньше именно 6-кратного шага, а не номинального.
В такой формулировке согласен.
Хотя и до 1.67млн в некоторых паттернах из 46080 даже стартовое число будет больше 5401e33 - потому что по какому-нибудь простому запретится нулевой остаток и первый же допустимый индекс в списке уже будет больше 5 (или 6 или даже 20). Т.е. в формуле для стартового числа в скобках вместо $(2+6i)$ будет нечто типа $(\{11,17,23,29\}+30i)$ (из 5-ти остатков по модулю 5 допустимы лишь 4, в данном случае без нулевого). А по модулю 7 может и например $11$ запретиться и тогда список начнётся скажем с $17$ и с коэффициентом $210i$.
В общем 6-кратный шаг удобен лишь своей простотой и удобством, ничего принципиального в нём не вижу.

-- 14.08.2022, 21:06 --

Yadryara
В 403 комплекте из интересного нашлось только:
S9-54-12H354:1811935220915213379443465020151486041: 12, 12, 12, 24, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, valids=14, ALL

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение14.08.2022, 22:08 
Заслуженный участник


27/06/08
4063
Волгоград
Yadryara в сообщении #1562733 писал(а):
Например, стартовое число

$106022957662445288229350041 + 440538835723387181869888800 \cdot (2 + 6\cdot0)$ в Ваших обозначениях и $p1-m$ в обозначениях VAL сам же VAL и не проверял. По невнимательности? Или же были какие-то причины считать, что эта проверка не нужна? Ждём ответа.
Посчитал, что вероятность получить искомую цепочку именно на этом шаге, когда ожидаемое количество проверок до успеха исчисляется триллионами, практически равна нулю и не стал заморачиваться.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение15.08.2022, 00:40 
Заслуженный участник


27/06/08
4063
Волгоград
$M(648)\ge 9$

(Оффтоп)

41831260011127811440887369168562481330188378193626991126324768526099733225758960973714569823007121727286116140699999997

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение15.08.2022, 11:46 
Заслуженный участник


20/08/14
11886
Россия, Москва
Yadryara
До границы 5401e33 просчитаны комплекты 403, 405, 408. Из интересного только показанная выше 14-ка.
В связи с значительным событием, рассказать о котором оставляю Вам, все следующие комплекты будут считаться до границы 1e35 пожалуй нет, до 2e35.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение15.08.2022, 12:19 
Аватара пользователя


29/04/13
8356
Богородский
Dmitriy40 в сообщении #1562755 писал(а):
В связи с значительным событием, рассказать о котором оставляю Вам,

Так уже все поняли :-)

Да, Демис нашёл новый Пентадекатлон. И тоже не заметил!

В 329-м комплекте, паттерн S9-36-587241 :

97648097903866012734106659998399641

Предыдущий рекорд побит аж в 55 раз !!!

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение15.08.2022, 12:34 
Заслуженный участник


20/08/14
11886
Россия, Москва
Yadryara
Кстати раз граница меньше 96e34, до которой были проверены куча комплектов (зелёные любой интенсивности в таблице), то теперь их все можно считать проверенными полностью.
До 1e35 счёт будет идти считанные минуты, можно считать до 2e35 чтобы поискать непрерывные 14-ки, двухкратное увеличение времени счёта на интервалах даже в десятки минут несущественно.
Вот теперь компиляция станет в разы дольше счёта ... :-( Как будет время буду думать что с ней делать.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение15.08.2022, 13:31 
Аватара пользователя


29/04/13
8356
Богородский
Dmitriy40 в сообщении #1562760 писал(а):
теперь их все можно считать проверенными полностью.

А то я не знаю :-)

Процитирую свои слова из переписки в триумвирате:
_______________________________________________

Я писал:

«а потом все втроём набросимся на более перспективные комплекты 35 — 295.»

Теперь, в связи с фантастической, умопомрачительной находкой, не надо уже на них набрасываться.

Они все уже обсчитаны гораздо выше. Так что неожиданно быстро сбылась моя мечта, одной фразой уже можно многое описать:

Полностью обсчитаны комплекты 0 — 318
____________________________________________

Dmitriy40 в сообщении #1562760 писал(а):
До 1e35 счёт будет идти считанные минуты, можно считать до 2e35 чтобы поискать непрерывные 14-ки,

Конечно. И об этом тоже уже написал. Но лучше всё же до 183е33.
_____________________________________________________________

Да, это странно, но надо бы снова считать до наименьшей (непрерывной) 14-ки, которая почти в 2 раза больше Пентадекатлона. Пока не могу привыкнуть к этому, но факт. В один круг конечно.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение15.08.2022, 13:48 
Заслуженный участник


27/06/08
4063
Волгоград
$M(420)\ge 8$

(Оффтоп)

176279031614354659011319812830225313338175217684419205733232689792319185039893153980986585437749033955063879579220708247940890622

Пока в качестве оценки сверху указал 127. Поправьте меня, пожалуйста, если знаете оценку получше.

-- 15 авг 2022, 13:55 --

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

Предыдущий рекорд побит аж в 55 раз !!!
Ого!
Если темпы обновления рекордов не снизятся, через пару-тройку лет дойдем до шестизначных. А там уж полным перебором снизу... :-)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3218 ]  На страницу Пред.  1 ... 109, 110, 111, 112, 113, 114, 115 ... 215  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group