Поиск простых чисел

[Droog_Andrey]

Т.е. Эратосфен.

[gris]

venco, я сейчас как раз проверяю в EXCEL Алгоритм и столкнулся с проблемой первичного размещения на жёстком диске массива всех нечётных чисел от $(2k-1)^2$ до $(2k+1)^2$ при очень больших $k$.
Каждое число я кодирую всего одним битом, и тем не менее мне не хватает места на диске D. Виндовс выдаёт ошибку "Lbcr gthtgjkyty/ Elfkbnt gjhyjuhfabxtcrbt abkmvs".
Я придумал, как реализовать алгоритм с помощью записи на диск нулевых битов в соответствии с указанным SerjeyMinsk порядком. Скорость получается просто умопомрачительная. В конце работы программы на диске остаются единичные биты, каждый из которых символизирует простое число. Но мне просто необходим для проверки алгоритма внешний жёсткий терабайтник. Если у кого есть, то я с благодарностью приму в дар во имя криптографии.

[Droog_Andrey]

Я ещё несколько страниц назад приводил ссылку на оптимизированный вариант решета Эратосфена, работающий сегментами в соответствии с размером процессорного кэша.

Такой алгоритм будет работать априори быстрее алгоритма, обрабатывающего сразу гигабайты.

[venco]

gris, хватит дразнить топик-стартера!

-- Ср сен 09, 2009 10:59:35 --

gris в сообщении #241738 писал(а):

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

Предлагаю оптимизацию - все нулевые биты сохранить в переменной bool zero, а единичные - в bool one.
Таким образом диск вообще не нужен. one обозначает все простые числа, а zero - составные.

[gris]

Скажите уж, что пожалели железяку подарить жадина-говядина :tongue:
Почему нет такого смайлика?
А сам алгоритм хранить в переменной "bool she eat"

[RIP]

gris в сообщении #241744 писал(а):

Почему нет такого смайлика?

Такого?

[gris]

RIP,спасибо! От Вас не только общей алгебре можно научиться, оказывается!

[SerjeyMinsk]

Я уже Вас вообще не понимаю.
Ну прикол для Вас то, что я пишу. Ну прикалывайтесь, потерплю. Ну ведь форум "Помогите решить / разобраться"
Вы же видите, что я ноль полнейший в формулах этих. Говорил-же опыт моего интереса к подобного рода исследованиям 2 месяца. Причины тоже называл. Я не могу отстаивать что-то на том уровне котором обладаете Вы. И Ваши знания в этой области я ни чем не умаляю. Вижу, что Вы специалисты. Но я просто не понимаю: Вы встречали людей, которые за три дня смогли сделать алгоритм поиска простых чисел, никогда не интересовавшись в жизни математикой со школьной скамьи? Вы сами сможете составить алгоритм отличающийся от решета таким подходом, как в ASSA? Я пока составил то, что смог запомнить в тот день. Возможно что-то упустил. Сам уже додумывал. Но уже очевидно то, что произошло в тот день что-то важное не только для меня, но и для Вас-же самих. Ну не может это быть так просто. Ну не верю я. Ведь то, что я знаю сейчас просто перевернет всю криптографию с ног на голову. Я узнал уже все об этой факторизации и что это такое. Так вот я убежден в том, что этот алгоритм имеет научную ценность именно потому, что только на основе ASSA я могу сделать разложение большого числа на простые множители ровно за столько времени за сколько она считает числа в 700 знаков (для RSA-2048 это ведь примерно столько знаков?), а не другим каким-либо методом. Пусть ASSA хоть в 100 раз считает дольше решета Эратосфена. Но метод работает. И я точно уверен, что такого быстрого разложения на множители нет во всем мире., какие бы еще непонятные для меня слова не говорилии и как бы вы не убеждали меня в том, что ASSA ничего нового из-себя не представляет.

gris
Если у тебя действительно есть сделанная в экселе ASSA скинь, пожалуйста, если ты просто не издеваешься надо мной.

[gris]

Сергей, я честное слово в некоторой растерянности. Вдруг ты на самом деле обижаешься? Поверь, издеваться никто и не думает, ну может быть проскакивают шутки и только. Иногда даже кажется, что это ты издеваешься, но не хотелось бы в это верить.
Я на самом деле подумал, что можно было бы реализовать твой алгоритм методом аппаратной записи на диск напрямую, без всяких экселей и паскалей, даже без операционной системы, используя только контроллер с изменяемым интерлейсингом в обратном направлении. Но для этого нужен большой внешний диск объёмом не менее 800 гигабайт. venco не хочет давать, а я не могу приобрести пока.
В Excel можно убедиться только в правильности алгоритма, в чём уже никто не сомневается. По скорости работы Excel естественно уступает программам, написанным на языке, близком к машинным кодам, который допускает оптимизацию. Может быть кто из знатоков программирования написал бы программу на самом низком уровне (с точки зрения компьютера).
Я специально ушёл от дискуссии, чтобы не обидеть тебя случайно неосторожными высказываниями, но не вытерпел и обратился к venco с наивной надеждой выцыганить жесткач. Но не прокатило.
Я ещё раз искренне желаю тебе удачи, уверяю, что и не думал дразнить тебя. Но к сожалению мой уровень знания компьютера не позволяет мне добавить что-то полезное в обсуждение.
.

[venco]

SerjeyMinsk в сообщении #241790 писал(а):

И я точно уверен, что такого быстрого разложения на множители нет во всем мире., какие бы еще непонятные для меня слова не говорилии и как бы вы не убеждали меня в том, что ASSA ничего нового из-себя не представляет.

А зачем спрашивали?
Таки да, ASSA ничего нового из себя не представляет, даже решето Эратосфена лучше, а оно совершенно не подходит для действительно больших чисел.
Вот пример гораздо более эффективного алгоритма:
http://www.alpertron.com.ar/ECM.HTM
Введите, например, число 100004400676048659579119862390733231

[SerjeyMinsk]

gris
А зачем было ручку тогда дарить, когда ты даже не реализовывал его нигде? Я думал, что хоть один человек на этом форуме понял, что ASSA это что-то ценное, а не просто какой-то никому ненужный хлам. И реально в знак уважения, а не в прикол какой. Это было огромной поддержкой моральной. Ведь еслибы я знал столько сколько вы наверняка нашел бы что-то еще в ASSA.
Я честно не понимаю как уже здесь разговаривать с вами и кому верить и кого слушать. Помочь никто не хочет разобраться. Объяснить что влияет на скорости, что требуется assa больше оперативной памяти, скорости процессора (хотя я не знаю даже как влияют Герцы в компьютере на скорости вычисления), памяти на винчестере. В чем проблема при работе возникает. Как они различаются с решетом Эратосфена.
Вот сестра приедет в начале ноября- привезет программу которая работает с большими числами, которую сделали по её просьбе её друзья. У меня-же до сих пор только то, что до миллиардных чисел считает. В паскале сколько не читал не врубаюсь вообще как там работать.
Вот и сижу и только и слушаю, что ничего этот assa из себя не представляет. Ну не может он не представлять ничего. Я уверен просто. Только вот помощников разобраться найти не могу. Надо было тогда заканчивать тему как и решил, жаль, что опять ввязался.

-- Ср сен 09, 2009 23:55:04 --

venco в сообщении #241798 писал(а):

SerjeyMinsk в сообщении #241790 писал(а):

И я точно уверен, что такого быстрого разложения на множители нет во всем мире., какие бы еще непонятные для меня слова не говорилии и как бы вы не убеждали меня в том, что ASSA ничего нового из-себя не представляет.

А зачем спрашивали?
Таки да, ASSA ничего нового из себя не представляет, даже решето Эратосфена лучше, а оно совершенно не подходит для действительно больших чисел.
Вот пример гораздо более эффективного алгоритма:
http://www.alpertron.com.ar/ECM.HTM
Введите, например, число 100004400676048659579119862390733231

Так почему решето Эратосфена не подходит для действительно больших чисел. И что это значит действительно большие. Сколько знаков?

Нету плагина посмотреть. Там факторизация?

-- Чт сен 10, 2009 00:03:34 --

venco
Как Вы считаете. Сколько по времени будет считать тычячезначные числа ASSA ? Приблизительно. День, месяц, год, десять лет? Если не лень в очередной раз, лучше точно. Вы-же знаете как можно это посчитать.

[Droog_Andrey]

SerjeyMinsk в сообщении #241790 писал(а):

Вы же видите, что я ноль полнейший в формулах этих.

Тогда на каком основании

SerjeyMinsk в сообщении #241790 писал(а):

я точно уверен, что такого быстрого разложения на множители нет во всем мире., какие бы еще непонятные для меня слова не говорилии и как бы вы не убеждали меня в том, что ASSA ничего нового из-себя не представляет.

???

Самый быстрый уиверсальный алгоритм разложения на множители на сегодняшний день - GNFS:
http://www.mersenneforum.org/showthread.php?t=4085

-- Ср сен 09, 2009 23:43:43 --

SerjeyMinsk в сообщении #241806 писал(а):

Как Вы считаете. Сколько по времени будет считать тычячезначные числа ASSA ?

Что значит "считать числа"?

[venco]

SerjeyMinsk в сообщении #241806 писал(а):

Вот и сижу и только и слушаю, что ничего этот assa из себя не представляет. Ну не может он не представлять ничего. Я уверен просто.

Это аргумент.

SerjeyMinsk писал(а):

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

Потому что у него сложность подсчёта всех простых чисел до $n$: $n\cdot log(log(n))$. У вашего алгоритма: $n \cdot log(n)$.
Если ограничиться диапазоном $(n-4\sqrt{n}+4,n)$, как у вас, то сложность будет $\sqrt{n}\cdot log(log(n))$ и $\sqrt{n}\cdot log(n)$ соответственно.

SerjeyMinsk писал(а):

И что это значит действительно большие. Сколько знаков?

Например 1000.
Для таких чисел и диапазона $(n-4\sqrt{n}+4,n)$ количество операций и время вычислений будут:
Эратосфен: порядка $10^{501}$ операций, порядка $10^{483}$ лет.
ASSA: порядка $10^{503}$ операций, порядка $10^{485}$ лет.

[SerjeyMinsk]

Droog_Andrey в сообщении #241811 писал(а):

???

На том основании, что ASSA раскладывает на два сомножителя составное число пропорционально количеству времени потраченного на поиск всех простых чисел в заданном диапазоне + 3 операции.

-- Чт сен 10, 2009 03:06:22 --

venco в сообщении #241818 писал(а):

Цитата:

Это аргумент.

Для меня да. Для Вас естественно нет.

Цитата:

Потому что у него сложность подсчёта всех простых чисел до $n$: $n\cdot log(log(n))$. У вашего алгоритма: $n \cdot log(n)$.
Если ограничиться диапазоном $(n-4\sqrt{n}+4,n)$, как у вас, то сложность будет $\sqrt{n}\cdot log(log(n))$ и $\sqrt{n}\cdot log(n)$ соответственно.

Например 1000.
Для таких чисел и диапазона $(n-4\sqrt{n}+4,n)$ количество операций и время вычислений будут:
Эратосфен: порядка $10^{501}$ операций, порядка $10^{483}$ лет.
ASSA: порядка $10^{503}$ операций, порядка $10^{485}$ лет.

Как раз учу что такое логарифмы чтобы понимать написанное про сложность расчета.

Узнал пока, что есть временная сложность алгоритма и есть пространственная. Вы привели получается обе эти сложности в формуле $\sqrt{n}\cdot log(n)$ Правильно?

То есть временная сложность алгоритма = количеству математических операций? Я правильно понял?

А как высчитывают пространственную?

[Droog_Andrey]

SerjeyMinsk в сообщении #241820 писал(а):

На том основании, что ASSA раскладывает на два сомножителя составное число пропорционально количеству времени потраченного на поиск всех простых чисел в заданном диапазоне + 3 операции.

Для 100-значного числа это количество времени в $10^{25}$ раз превышает возраст вселенной, в то время как GNFS справляется за несколько часов.