Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 20 21 22 23 24 [25] 26 27 28 29 .. 31   вперед  Ctrl
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
alex55555
Member

Откуда:
Сообщений: 2100
Gennadiy Usov
Самое простое решение этой проблемы, это - определять простые числа рядом с серединой БРЧ.

Не простое оно.

В рамках ограничений мы знаем всё о простых числах. Далее есть зона вне ограничений. Так вот в этой зоне нам не хватает памяти. И вы, предлагая середину, действуете как будто ограничений нет, но они никуда не делись. То есть вам придётся всё так же перебирать миллионы чисел и проверять их простоту. Я вам напомню - это годы на одно большое число. Так что один промах - год работы. Ну и ваши потуги уменьшить количество промахов на одну шестую, седьмую и т.д. выглядят, конечно, интересно, но количество миллионов для проверки от этого сокращается совсем незаметно. Для перебора всё равно остаётся недоступное для наших ограничений количество.
12 мар 19, 13:25    [21830206]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 40522
Gennadiy Usov
mayton
А какую задачу вы решаете теперь?
Я почему спрашиваю. Топика стартовал как генерация последовательности primes методом Эратосфена.
А это и есть продолжение идеи Эратосфена.

При определении различных БРЧ, построеных на идее Эратосфена, было замечено, что по краям этих БРЧ есть "дыры", где нет простых чисел.
Поскольку распределение простых чисел почти равномерное на диапозоне, то можно предположить, что в других местах БРЧ распределение простых чисел будет чаще.

Самое простое решение этой проблемы, это - определять простые числа рядом с серединой БРЧ.

Что и было показано на БРЧ, начиная с БРЧ-2-3 и заканчивая БРЧ-13-41.
Далее - маловата ячейка.

Нет. Эратосфен - точен. Он не пропускает ни одного простого.

А ваша идея - это вариации на тему чисел Мерсенна с более тяжёлым методом генерации кандидатов.
В мерсенне мы можем просто добавить ещё один старший бит. И кандидат готов.

Почему я и спрашиваю. Вы заняты просто поиском наибольшего простого?
Или генерацией последовательности? Это две разные задачи.
12 мар 19, 13:36    [21830215]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
alex55555
Не простое оно.

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

mayton
Нет. Эратосфен - точен. Он не пропускает ни одного простого.

А ваша идея - это вариации на тему чисел Мерсенна с более тяжёлым методом генерации кандидатов.
В мерсенне мы можем просто добавить ещё один старший бит. И кандидат готов.

Почему я и спрашиваю. Вы заняты просто поиском наибольшего простого?
Или генерацией последовательности? Это две разные задачи.
Сразу отвечаю на два сообщения.

Есть попытка развить идею множества последовательностей целых чисел, опирающихся на реперные числа.21818158

Далее считать не собираюсь - компьютер "не позволит".
Если кому-то интересно...

Например, брал середину БРЧ-11-31 и прибавлял 65 раз размер БРЧ-12-37.
Сделал 130 построений (+-2).

Из них: 30 простых чисел, причем 5 "двойных" - при одном прибавлении.
12 мар 19, 13:47    [21830227]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
alex55555
Member

Откуда:
Сообщений: 2100
Gennadiy Usov
Из них: 30 простых чисел, причем 5 "двойных" - при одном прибавлении.

Это в начале числового ряда. Здесь всё давно изучено вдоль и поперёк. А в районе миллионных порядков вероятность найти простое - один к миллионам, а потому некоторое её повышение (например вместо одни к 3 миллионам будет 1 к одному миллиону) даст нам необходимость проверять этот самый миллион, который "мимо кассы", что выливается в отсутствующее у нас время. Ну или в отсутствующие вычислительные ресурсы.

Второе направление. При генерации последовательностей мы упираемся в память. Вы опять предлагаете по сути всё ту же рекурсию на основе всех известных простых, а для них нужна память, которая, как я вам говорил, кончится где-то в районе 280.

В целом - вы занимательно возитесь с алгоритмом, который вообще непонятно где применять. Хотя вспомнил - можно раза в полтора-два ускорить процедуру, выполняемую раз в год и занимающую несколько секунд. Вот и всё.

Хотя дальнейшее движение может вас куда-то и приведёт, но пока что вы снова и снова демонстрируете "достижения", которые отвергнуты уже страниц 10-15 назад. Зачем так злобно повторяться?
12 мар 19, 14:53    [21830321]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
alex55555
Gennadiy Usov
Из них: 30 простых чисел, причем 5 "двойных" - при одном прибавлении.
Это в начале числового ряда. Здесь всё давно изучено вдоль и поперёк. А в районе миллионных порядков вероятность найти простое - один к миллионам, а потому некоторое её повышение (например вместо одни к 3 миллионам будет 1 к одному миллиону) даст нам необходимость проверять этот самый миллион, который "мимо кассы", что выливается в отсутствующее у нас время. Ну или в отсутствующие вычислительные ресурсы.

В целом - вы занимательно возитесь с алгоритмом, который вообще непонятно где применять. Хотя вспомнил - можно раза в полтора-два ускорить процедуру, выполняемую раз в год и занимающую несколько секунд. Вот и всё.

Хотя дальнейшее движение может вас куда-то и приведёт, но пока что вы снова и снова демонстрируете "достижения", которые отвергнуты уже страниц 10-15 назад. Зачем так злобно повторяться?
Вы совершенно не хотите ничего читать в сообщении и повторяете заученную фразу: нам не хватит времени и памяти.

В приведённом сообщении говорилось о том, что при определении 130-ти чисел в районе от 7,52102E+12 до 4,82448E+14 было найдено 30 простых чисел, из которых 10 простых чисел попарно расположены на расстоянии 4.

Так где здесь миллионы времени и памяти?
12 мар 19, 15:25    [21830385]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
alex55555
Member

Откуда:
Сообщений: 2100
Gennadiy Usov
В приведённом сообщении говорилось о том, что при определении 130-ти чисел в районе от 7,52102E+12 до 4,82448E+14 было найдено 30 простых чисел, из которых 10 простых чисел попарно расположены на расстоянии 4.

Так где здесь миллионы времени и памяти?

На расстоянии 2100000000 будут как раз миллионы. Ну пусть даже сотни тысяч, но проверять каждое вы будете неделю на суперкомпьютере. Сколько тысячелетий вам потребуется?

Ваш подход не учитывает всех простых вне выбранной очень маленькой группы, вот эти простые на миллионных расстояниях и загадят вам ваши ожидания. Это было бы очевидно и вам, если бы вы отвлеклись от идеи-фикс.
12 мар 19, 20:19    [21830699]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Dima T
Member

Откуда:
Сообщений: 13634
2100000000 нафиг не надо на практике, т.к. достаточно 22048. Все что больше 22048 интересно чисто с научной точки зрения, т.е. в каких порядках мы огребем проблемы генерации простых чисел.
12 мар 19, 20:42    [21830708]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 40522
Тогда топик пора закрывать. Генерация пары для RSA формально решена. И работает.
12 мар 19, 21:00    [21830722]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
alex55555
Member

Откуда:
Сообщений: 2100
Dima T
2100000000 нафиг не надо на практике, т.к. достаточно 22048.

На практике за миллионы дают 50 килобаксов, а за ускорение операции, требующейся раз в год и длительностью в секунду в два раза, не дадут ничего.
13 мар 19, 10:45    [21831043]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 40522
Не для RSA.

А для решения топовых задач по поиску максимально больших чисел:

Давайте сначала ознакомимся с программно-аппартной архитектурой тех комплексов
которые эти топовые числа считают. Потом посчитаем хоть какой-то коэффициент
параллелизма. И решим стоит-ли этим вообще заниматься. Или эти 50 килобаксов
мы и так заплатим за электричество покупку железа и оплату Гугл или Амазон
аккаунтов.

Это в напоминание того что данный топик - является топиком потоков созднания
и к реальному рекорду он не имеет отношения.
13 мар 19, 11:30    [21831092]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
alex55555
Member

Откуда:
Сообщений: 2100
mayton
Или эти 50 килобаксов мы и так заплатим за электричество покупку железа и оплату Гугл или Амазон аккаунтов.

Да, при использовании известных алгоритмов - бесполезное занятие. Нужен алгоритм, сжимающий информацию о простых в миллионы раз, тогда можно искать прицельно. Либо алгоритм, проверяющий простоту как-то "по простому", в смысле не требуя огромных затрат вычислительных ресурсов.
13 мар 19, 12:32    [21831171]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 40522
alex55555
mayton
Или эти 50 килобаксов мы и так заплатим за электричество покупку железа и оплату Гугл или Амазон аккаунтов.

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

Вопросы сжатого хранения простых мы тоже поднимали. Несколько лет назад.
Но даже не доходя до 2^2048 у нас уже закончится кремний и металл
на планете земля для поддержки такой базы.
13 мар 19, 12:40    [21831195]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4489
mayton,

мы ещё до квадратичного решета не дошли, есть куда расти :-)
13 мар 19, 13:33    [21831278]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 40522
Хорошо. Давайте моделировать на макетах и смотреть как оно работает.

Я даже могу дополнить свою MindMap новыми идеями.
13 мар 19, 13:52    [21831312]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Все пропустили сообщение 21826920. Нет ответов.

А если взглянуть на данное сообщение, то что оно предлагает:
на диапазоне от М до N можно найти все составные числа, следовательно, на этом диапазоне остальные числа - простые.

Теперь представим:
диапазон от 2^1024 до (2^1024 + 10000).

То есть, надо найти в диапазоне около 3333 чисел.

Где громадные массивы и огромное время?
Ведь всего нужно определить около 3333 чисел.
14 мар 19, 06:40    [21831991]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Dima T
Member

Откуда:
Сообщений: 13634
Gennadiy Usov
на диапазоне от М до N можно найти все составные числа, следовательно, на этом диапазоне остальные числа - простые.

Теперь представим:
диапазон от 2^1024 до (2^1024 + 10000).

То есть, надо найти в диапазоне около 3333 чисел.

Не 3333, а N/ln(N) - M/ln(M) примерно 14 чисел

Gennadiy Usov
Где громадные массивы и огромное время?

Чтобы проверить классическим способом число порядка 2^1024 надо поделить его на все простые до 2^512, а это потребует громадные массивы и огромное время.
14 мар 19, 07:30    [21832001]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Dima T
Gennadiy Usov
на диапазоне от М до N можно найти все составные числа, следовательно, на этом диапазоне остальные числа - простые.
Теперь представим:
диапазон от 2^1024 до (2^1024 + 10000).
То есть, надо найти в диапазоне около 3333 чисел.
Не 3333, а N/ln(N) - M/ln(M) примерно 14 чисел
Gennadiy Usov
Где громадные массивы и огромное время?
Чтобы проверить классическим способом число порядка 2^1024 надо поделить его на все простые до 2^512,
а это потребует громадные массивы и огромное время.
Я говорил про все числа из серии 6хК+1 и 6хК-1. Их будет 3333.

Надо просто поискать среди этих 3333 чисел составные числа (которые будут "выбиваться" из массива 3333 чисел).
Остальные будут простые.

Например, число 5 "выбивает" из 3333 сразу 700 чисел.
число 7 "выбивает" из 3333 сразу около 400 чисел (могут быть числа, кратные 5).
число 11 "выбивает" из 3333 сразу около 300 чисел (могут быть числа, кратные 5 и 7).

и т.д.
14 мар 19, 07:49    [21832006]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
alex55555
Member

Откуда:
Сообщений: 2100
mayton
Вопросы сжатого хранения простых мы тоже поднимали. Несколько лет назад.
Но даже не доходя до 2^2048 у нас уже закончится кремний и металл
на планете земля для поддержки такой базы.

Полином Эйлера не требует памяти, кроме памяти под программу. Вообще не требует. Вот это - приличный коэффициент сжатия.
kealon(Ruslan)
мы ещё до квадратичного решета не дошли, есть куда расти

Геннадию чего попроще надо - метод Ферма.
14 мар 19, 12:14    [21832333]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
alex55555
Member

Откуда:
Сообщений: 2100
Gennadiy Usov
Надо просто поискать среди этих 3333 чисел составные числа (которые будут "выбиваться" из массива 3333 чисел).
Остальные будут простые.

Вот вы и поищите. Через несколько тысяч лет наверняка придёт понимание, что где-то вы что-то упустили.
14 мар 19, 12:16    [21832335]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 40522
Полином Эйлера - это просто забавное совпадение.
Сколько еще таких полнинов? Полином Усова?
Сколько нам надо памяти под хранение всех
формул полиномов для primes хотя-бы до миллиона?
14 мар 19, 12:27    [21832362]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
alex55555
Member

Откуда:
Сообщений: 2100
mayton
Сколько нам надо памяти под хранение всех
формул полиномов для primes хотя-бы до миллиона?

Не знаю. Возможно - очень мало.
14 мар 19, 12:41    [21832384]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
alex55555
kealon(Ruslan)
мы ещё до квадратичного решета не дошли, есть куда расти
Геннадию чего попроще надо - метод Ферма.
Метод Ферма - это комплекс вычислений
(пусть специалисты прикинут, сколько надо вычислений для одного числа),
направленых на определение того, что выбранное число является составным числом.

И не более.

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

Все остальные числа вида 6хК+1 или 6хК-1 можно признать, как и в методе Ферма, простыми.
14 мар 19, 12:47    [21832391]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
mayton
Полином Эйлера - это просто забавное совпадение.
Сколько еще таких полнинов? Полином Усова?
В этом что-то есть...
14 мар 19, 12:49    [21832393]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 40522
Не увлекайся сильно
14 мар 19, 12:50    [21832395]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Я проверил диапазон от 11100000 до 11100101.
101 число.

По схеме 6хК+1 и 6хК-1 имеем 34 числа.
Из них - 11 - простые числа.

Оставшиеся 23 числа "выбили" следующие числа:
5 - 7 раз
7 - 4 раза
11 - 3 раза
13 - 2 раза
23 - 2 раза
и по 1 разу: 17, 31, 59, 67, 107
14 мар 19, 12:55    [21832401]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 20 21 22 23 24 [25] 26 27 28 29 .. 31   вперед  Ctrl
Все форумы / Программирование Ответить