2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 5, 6, 7, 8, 9, 10, 11 ... 72  След.
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение08.03.2024, 12:26 
Заслуженный участник


20/08/14
11714
Россия, Москва
Судя по абстракту там обосновали вероятностную модель появления кортежей. Т.е. пытаться их прогнозировать (где они точно встретятся) - заведомо неосуществимо.
Саму статью не смотрел, но чего-то сомневаюсь что построенная модель хоть как-то заметно поможет в выборе небольшого интервала перебора для поиска заданного паттерна/кортежа. И уж тем более для первого (наименьшего) вхождения/решения.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение08.03.2024, 16:45 


23/02/12
3341
Dmitriy40 в сообщении #1632200 писал(а):
Саму статью не смотрел, но чего-то сомневаюсь что построенная модель хоть как-то заметно поможет в выборе небольшого интервала перебора для поиска заданного паттерна/кортежа. И уж тем более для первого (наименьшего) вхождения/решения.
А какой наибольший интервал перебора проверен?

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение08.03.2024, 22:57 
Заслуженный участник


20/08/14
11714
Россия, Москва
vicvolf в сообщении #1632216 писал(а):
А какой наибольший интервал перебора проверен?
Очень сильно зависит от паттерна (k-tuples), для некоторых проверено очень далеко, для многих лишь примерно до $10^{31}$, для того что в этой теме 19-252 я проверил лишь до $10^{24}$ (примерно, за почти год, это почти $10^{18}$ кандидатов). Ещё для многих и многих проверено практически тотально до $9\cdot10^{18}$ (это несколько боинк проектов считали), там найдены все цепочки что вообще искали (а искали не все возможные, это собственно неопределённое понятие), но даже и это миллионы цепочек/кортежей.
В общем всё зависит что именно искать.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение09.03.2024, 10:00 


23/02/12
3341
Dmitriy40 в сообщении #1632256 писал(а):
Ещё для многих и многих проверено практически тотально до $9\cdot10^{18}$ (это несколько боинк проектов считали), там найдены все цепочки что вообще искали (а искали не все возможные, это собственно неопределённое понятие), но даже и это миллионы цепочек/кортежей.
А как распределяются вычисления между участниками боинк проектов, чтобы они не считали одинаковые промежутки?

-- 09.03.2024, 10:03 --

Dmitriy40 в сообщении #1632256 писал(а):
для того что в этой теме 19-252 я проверил лишь до $10^{24}$ (примерно, за почти год, это почти $10^{18}$ кандидатов).
Вы потратили почти год, а может кто-то в проектах уже считал этот интервал?

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение09.03.2024, 12:42 
Заслуженный участник


20/08/14
11714
Россия, Москва
vicvolf в сообщении #1632282 писал(а):
Вы потратили почти год, а может кто-то в проектах уже считал этот интервал?
Кто-то точно этот интервал уже считал, и не один раз. Даже я сам его уже считал, десятки раз.
НО! Простых чисел очень много, и структур на них можно понастроить очень разных, потому искать и хранить на будущее просто абсолютно все простые - идиотизм (и места не хватит, и снова найти их быстрее чем считать из БД такого размера), ищутся всегда какие-то структуры на множестве простых (некие подмножества), и вопрос какие именно это структуры/подмножества.
Вот например интервал до 1e15 я выше считал два раза, для двух таблиц (num17 и num15), хотя он был мною же просчитан ещё лет 10 назад, плюс потом в боинк, плюс для поиска 19-252 тоже был просчитан, плюс ещё для множества разных других паттернов тоже был каждый раз снова просчитан - потому что каждый раз искались разные структуры/подмножества на простых числах и прочие игнорировались.

vicvolf в сообщении #1632282 писал(а):
А как распределяются вычисления между участниками боинк проектов, чтобы они не считали одинаковые промежутки?
Можно по разному, но наиболе просто и логично выявить (или задать) интервал который считается в среднем около (полу)часа и поделить всю задачу/работу на такие интервалы и выдавать каждому компу свой интервал, ведь расчёт внутри каждого интервала независим (за исключением начальной инициализации, но это секунды). Есть некоторые тонкости и хитрости, но в общем так.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение09.03.2024, 14:50 


23/02/12
3341
Dmitriy40 в сообщении #1632256 писал(а):
для того что в этой теме 19-252 я проверил лишь до $10^{24}$
Я прикинул, чтобы встретить данный кортеж надо проверить не меньше, чем до $10^{36}$.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение09.03.2024, 15:54 
Заслуженный участник


20/08/14
11714
Россия, Москва
vicvolf в сообщении #1632305 писал(а):
Я прикинул, чтобы встретить данный кортеж надо проверить не меньше, чем до $10^{36}$.
Это явно сильно завышенная оценка, я выше по методу Yadryara посчитал что до 5e25 должно быть в среднем 154 цепочек (возможно с лишними простыми между нужными). Если даже как для более коротких на каждые 30-40 цепочек с лишними простыми приходится одна правильная (без лишних простых), то всё равно до 5e25 должно быть 4-5 искомых цепочек.
Оценка по тренду по более коротким цепочкам вообще даёт оценку первой цепочки до 2e24.

Оцените своим методом ожидаемый интервал для центральных 17 чисел из этого паттерна (17-240) и сравниtе с реально найденным решением практически на 1e21 (при том что оценка по методу Yadryara даёт около 34 цепочек с лишними простыми в том же интервале).
И оцените требуемый интервал для центральных 15 чисел из этого паттерна (15-228), реально же цепочка нашлась в 2.08e18.
Будет понятно насколько Ваша оценка завышена.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение09.03.2024, 17:43 


23/02/12
3341
Dmitriy40 в сообщении #1632310 писал(а):
Оцените своим методом ожидаемый интервал для центральных 17 чисел из этого паттерна (17-240) и сравниtе с реально найденным решением практически на 1e21 И оцените требуемый интервал для центральных 15 чисел из этого паттерна (15-228), реально же цепочка нашлась в 2.08e18.
При $17$ получилось $10^{31}$. При 15 получилось $10^{26}$. Оценки ориентировочные. Возможно завышены.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение09.03.2024, 18:06 
Аватара пользователя


29/04/13
8070
Богородский
vicvolf в сообщении #1632305 писал(а):
Я прикинул, чтобы встретить данный кортеж надо проверить не меньше, чем до $10^{36}$.

:shock: Эдак никакого ха-ха не хватит. Предположим, что Dmitriy40 сможет ускорить свою прогу ещё раз эдак в пять, до 5е24/год. Это что же 200 миллиардов лет считать ??

Так что прикидку в студию, плиз.

Я ещё в июне делал завышенные прикидки:

Yadryara в сообщении #1598211 писал(а):
Ведь для 17-к простое перемножение предсказывает одну на 6e23, а для 19-к — одну на 2.7e26.

Тот метод был совсем прост. Но обратите внимание: 26-й порядок, а не 36-й.

Затем я довольно долго возился с кэфами, но потом отказался и придумал другой метод, который подробно описал здесь, в теме, на 3-4 страницах. Кстати, не сразу заметил похвалу от гуру:

Dmitriy40 в сообщении #1629560 писал(а):
Yadryara
Слушайте, а ведь отличный метод оценки! :appl:
Пусть и грязных цепочек. Зато хоть какое-то нормальное (математическое) обоснование где они должны быть хотя бы в среднем, а не гадание по трендам.

Затем я хотел ещё точнее оценить, по валидс18, привёл свою прогу, но почему-то оба собеседника промолчали в ответ.

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

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение09.03.2024, 20:18 
Заслуженный участник


20/08/14
11714
Россия, Москва
vicvolf в сообщении #1632315 писал(а):
При $17$ получилось $10^{31}$. При 15 получилось $10^{26}$. Оценки ориентировочные. Возможно завышены.
Ну то есть грубо по 5 порядков на каждые две единицы длины. А практика показывает что реально всего лишь около двух порядков на две единицы длины (ну и коэффициент запаса скажем от 1/3 до 3). Так что нет, 5 порядков это очень сильно завышено.

Yadryara в сообщении #1632317 писал(а):
но почему-то оба собеседника промолчали в ответ.
Я недавно внимательно на неё посмотрел (убрав всё лишнее) и не увидел ничего нового по сравнению с уже выполненной оценкой (только лишь точность чуть повыше, не 19 цифр, а 50, что в общем не суть).

-- 09.03.2024, 21:09 --

Yadryara в сообщении #1632317 писал(а):
Предположим, что Dmitriy40 сможет ускорить свою прогу ещё раз эдак в пять, до 5е24/год.
Вчера-сегодня пришла новая идея как ускорить программу, за счёт упрощения проверок на допустимые остатки, оценка даёт примерно 3.5 раза рост скорости плюсом к ускорению за счёт КТО (отказа от линейного перебора и переходу к перебору лишь допустимых вариантов, что даёт ускорение 3.34 раза). Суммарно пока получается 12 раз по отношению к работающей версии. Но это синтетический тест, не на реальных данных. Реальная скорость возможно упадёт раз до 10.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение10.03.2024, 08:25 
Аватара пользователя


29/04/13
8070
Богородский
Dmitriy40 в сообщении #1632329 писал(а):
Суммарно пока получается 12 раз по отношению к работающей версии.

Я ориентировался вот на это, совсем недавнее:

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


Dmitriy40 в сообщении #1632329 писал(а):
ускорению за счёт КТО (отказа от линейного перебора и переходу к перебору лишь допустимых вариантов, что даёт ускорение 3.34 раза)

Я это понимаю так.

Счёт пойдёт с какого-то места из диапазона 0-78е23 и в каком-то порядке, но точно не по возрастанию и не по убыванию. При этом будут заново(!) пересчитываться числа из диапазона 0-10е23, на который ушёл почти год счёта.

Хотя, может это уже и не такая проблема как раньше, ежели 10-12-кратное ускорение будет достигнуто. Месяц пересчёта.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение10.03.2024, 10:36 


23/02/12
3341
Yadryara в сообщении #1632317 писал(а):
Так что прикидку в студию, плиз.
Я ничего нового не изобретал. Есть первая гипотеза Харди-Литтлвуда о количестве k-кортежей на интервале $x$: $\pi(x,k) \sim \frac{Cx}{\ln^k(x)}$, где постоянная $C$ зависит от структуры кортежа. В данном случае я хотел просто грубо оценить порядок величины $x$ до первого кортежа, поэтому предположил значение $\pi(x,k)=1$, а значение $C$ вообще не учитывал. Наверно так делать нельзя, так как значение $C$ при большом значение $k$ велико и формула асимптотическая. До этого я проверял гипотезу при небольших значениях $k$ и большом количестве кортежей и она давала хорошие результаты.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение10.03.2024, 12:58 
Заслуженный участник


20/08/14
11714
Россия, Москва
Yadryara в сообщении #1632357 писал(а):
Я это понимаю так.
Счёт пойдёт с какого-то места из диапазона 0-78е23 и в каком-то порядке, но точно не по возрастанию и не по убыванию. При этом будут заново(!) пересчитываться числа из диапазона 0-10е23, на который ушёл почти год счёта.
Хотя, может это уже и не такая проблема как раньше, ежели 10-12-кратное ускорение будет достигнуто. Месяц пересчёта.
В принципе правильно, только в деталях несколько по другому: я пока отказался от учёта 67 и по КТО перебираю лишь 61#, что в 1.4 раза медленнее (ускорение не 4.66, а 3.34 раза), зато можно идти с шагом 61#=1.173e23 и не пересчитывать то что уже насчитано (10 полных интервалов 61#). Зато пока скорость внутреннего цикла более чем вдвое выше и в итоге скорость уже не х12, а лишь х7 (вчера была ошибка в программе) от работающей программы. Если решение встретится до 6e24 (а должно бы и до 2-3e24), то так оно будет найдено раньше (за 190 дней) чем перебором по 67#. Если не встретится до 67#, будут насчитаны 17 лишних интервалов 61# (ещё за 80 дней), потом переделаю перебор на 67# и пропущу первую итерацию чтобы не повторять. Или брошу эту затею.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение10.03.2024, 15:29 


23/02/12
3341
Yadryara в сообщении #1632317 писал(а):
. Это что же 200 миллиардов лет считать ??
У Вас все как-то наоборот. Для чего нужна предварительная оценка трудоемкости счета задачи? Для того, чтобы не тратить время на пока неразрешимые.

-- 10.03.2024, 15:30 --

Dmitriy40 в сообщении #1632376 писал(а):
Или брошу эту затею.
Вот именно!

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение10.03.2024, 15:41 
Заслуженный участник


20/08/14
11714
Россия, Москва
vicvolf в сообщении #1632390 писал(а):
Для чего нужна предварительная оценка трудоемкости счета задачи? Для того, чтобы не тратить время на пока неразрешимые.
Только оценка должна быть более-менее точной, а не завышенной на 10 порядков.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1076 ]  На страницу Пред.  1 ... 5, 6, 7, 8, 9, 10, 11 ... 72  След.

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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