2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Сколько HD по 1Tb нужно для хранения 10^30 простых чисел?
Сообщение17.03.2010, 19:06 
venco в сообщении #298702 писал(а):
Уверяю Вас, вы не знаете такого способа.

Согласен. Минут пять назад проверил в Математике. При больших праймориалах он не работает. Ну ничего, всё равно всем благодарен за информацию и помощь ;) Заказал через Интернет книжку почитать на эту тему... Если там будет то, что мне хочется увидеть там, то сообщу.

 
 
 
 Re: Сколько HD по 1Tb нужно для хранения 10^30 простых чисел?
Сообщение17.03.2010, 19:20 
venco в сообщении #298702 писал(а):

ananova в сообщении #298610 писал(а):
Поэтому мне нужен единомышленник (единомышленники), которые могут вычислить праймориал больше чем 12 млн цифр.. Как тут посчитал venco - это несколько десятков мегабайт всего навсего.
Это довольно тривиальная задача. Произведение первых $10^7$ простых чисел (вплоть до $179424673$) считается за время меньше минуты.
В бинарном виде 32 мегабайта (выше я немного ошибся).
В десятичном виде $77919922$ цифр:
$3380445109538286518178...30065441278013328441066732954520433703644022980910$

Все простые числа считаются известными?
Каковы условия задачи? - уточните.

 
 
 
 Re: Сколько HD по 1Tb нужно для хранения 10^30 простых чисел?
Сообщение17.03.2010, 22:57 
fer1800 в сообщении #298749 писал(а):
Все простые числа считаются известными?
Каковы условия задачи? - уточните.

Нет ничего проще - побить рекорд 2001 года для простых, равных значению праймориала+1.
Сложность заключается в проверке на простоту праймориала+1. Как показал venco - проблема только в этом.

[Сначала надо ознакомиться с передовыми методами по проверке на простоту, затем уже браться за дело, если будет найден алгоритм, не уступающий использованному, при побитии рекорда.]

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

Но в этом я тоже стал сильно сомневаться.

 
 
 
 Re: Сколько HD по 1Tb нужно для хранения 10^30 простых чисел?
Сообщение17.03.2010, 23:30 
Аватара пользователя
Существует программа PrimeForm, приспособленная для сравнительно быстрой проверки на простоту больших чисел. К сожалению, не любых, но с числами вида $n\#\pm 1$ она справляется. Я не знаю, какая у неё верхняя граница, но с миллионом цифр она справляется, если хватит терпения и питание компьютера случайно не отключится. Однако для установления рекорда она не годится, а более быстрой программы я не знаю (программу, предназначенную для проверки специально чисел Мерсенна, не считаем).

 
 
 
 Re: Сколько HD по 1Tb нужно для хранения 10^30 простых чисел?
Сообщение18.03.2010, 00:32 
Аватара пользователя
Someone в сообщении #298827 писал(а):
Существует программа PrimeForm,

PrimeForm уже устарела - ее наследник OpenPFGW: http://sourceforge.net/projects/openpfgw/files/

 
 
 
 Re: Сколько HD по 1Tb нужно для хранения 10^30 простых чисел?
Сообщение18.03.2010, 08:34 
Википедия сообщает:

Проект по проверке проблемы Гольдбаха сообщает, что были вычислены все простые числа до $10^{18}$. Это составляет 24 739 954 287 740 860 простых чисел, но они не были сохранены.

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

 
 
 
 Re: Сколько HD по 1Tb нужно для хранения 10^30 простых чисел?
Сообщение18.03.2010, 08:44 
Аватара пользователя
Someone в сообщении #298437 писал(а):
Количество цифр в десятичной записи данного числа.

Зачем десятичная, двоичную запись надо юзать!

Кстати, решето Эратосфена до каких чисел оказывается эффективным?

 
 
 
 Re: Сколько HD по 1Tb нужно для хранения 10^30 простых чисел?
Сообщение28.05.2010, 19:37 
ananova в сообщении #298820 писал(а):
Если найти "прорывной" способ определения на простоту, сравнимый с эффективностью проверки чисел Мерсенна, то можно и на большее замахнуться.
Но в этом я тоже стал сильно сомневаться.

Есть детерминированный алгоритм проверки числа на простоту, с полиномиальной сложностью (праймориал +- 1 под него подходит).
Операций по сравнению с Мерсеновским алгоритмом будет больше в 4*(Количество простых в праймориале) раза.
А здесь его результаты:
http://dxdy.ru/post324691.html#p324691
http://dxdy.ru/post324794.html#p324794

Кстати индийский алгоритм AKS тоже полиномиальный и детерминированный, почему его нельзя использовать?

Кто деньги пробьет под это дело? 8-)

 
 
 
 Re: Сколько HD по 1Tb нужно для хранения 10^30 простых чисел?
Сообщение28.05.2010, 22:05 
lorents в сообщении #324997 писал(а):
Есть детерминированный алгоритм проверки числа на простоту, с полиномиальной сложностью (праймориал +- 1 под него подходит).
Операций по сравнению с Мерсеновским алгоритмом будет больше в 4*(Количество простых в праймориале) раза.


И еще, алгоритм детерминированной проверки чисел Мерсена, насколько я понимаю, не распараллеливается.
Если я прав, чтобы проверить число Мерсена $2^{43112609}-1$ надо выполнить 43112609 двойных операций (умножить, сложить) по модулю этого большого числа. Смотрите Тест Люка-Лемера на Википедии. Это делается на одном компьютере.

Предлагаемый алгоритм распараллеливается по количеству простых в праймориале.

 
 
 
 Re: Сколько HD по 1Tb нужно для хранения 10^30 простых чисел?
Сообщение29.05.2010, 09:48 
lorents в сообщении #325041 писал(а):
И еще, алгоритм детерминированной проверки чисел Мерсена, насколько я понимаю, не распараллеливается.


алгоритм можно не распараллеливать, а оставить неизменным, а данные исходные разбить и куски их раздать друзьям по компьютерам. Кому повезёт, тот и герой!

 
 
 
 Re: Сколько HD по 1Tb нужно для хранения 10^30 простых чисел?
Сообщение30.05.2010, 01:09 
Аватара пользователя
ananova в сообщении #298429 писал(а):
100 байт займет одно простое число.

venco в сообщении #298490 писал(а):
100 бит, или 13 байт.

А сколько символов (цифр) в числе о котором Вы говорите?
Насколько знаю 1 байт - 1 символ.

 
 
 
 Re: Сколько HD по 1Tb нужно для хранения 10^30 простых чисел?
Сообщение30.05.2010, 11:07 
SerjeyMinsk в сообщении #325410 писал(а):
ananova в сообщении #298429 писал(а):
100 байт займет одно простое число.

venco в сообщении #298490 писал(а):
100 бит, или 13 байт.

А сколько символов (цифр) в числе о котором Вы говорите?
Насколько знаю 1 байт - 1 символ.


Уважаемый, в одном байте 8 бит :lol:

 
 
 
 Re: Сколько HD по 1Tb нужно для хранения 10^30 простых чисел?
Сообщение30.05.2010, 11:17 
Аватара пользователя
lorents в сообщении #325465 писал(а):
SerjeyMinsk в сообщении #325410 писал(а):
ananova в сообщении #298429 писал(а):
100 байт займет одно простое число.

venco в сообщении #298490 писал(а):
100 бит, или 13 байт.

А сколько символов (цифр) в числе о котором Вы говорите?
Насколько знаю 1 байт - 1 символ.


Уважаемый, в одном байте 8 бит :lol:

И что?

 
 
 
 Re: Сколько HD по 1Tb нужно для хранения 10^30 простых чисел?
Сообщение30.05.2010, 11:21 
Аватара пользователя
SerjeyMinsk в сообщении #325468 писал(а):
И что?
10 бит - это примерно 3 десятичных цифры

 
 
 
 Re: Сколько HD по 1Tb нужно для хранения 10^30 простых чисел?
Сообщение30.05.2010, 11:30 
Аватара пользователя
ananova
Цитата:
Сколько HD по 1Tb нужно для хранения 10^30 простых чисел?

1 HDD, если пользоваться архиватором.

 
 
 [ Сообщений: 55 ]  На страницу Пред.  1, 2, 3, 4  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group