Сколько HD по 1Tb нужно для хранения 10^30 простых чисел?

[lorents]

age в сообщении #325473 писал(а):

ananova

Цитата:

Сколько HD по 1Tb нужно для хранения 10^30 простых чисел?

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

Какой будет коэффициент сжатия?

[SerjeyMinsk]

Xaositect в сообщении #325471 писал(а):

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

И что?

10 бит - это примерно 3 десятичных цифры

Почему?
8 бит = 1байт = 1 символ = формат представления одного числа (о-9)

[yk2ru]

в 3 байта можно затолкнуть 8 десятичных символов из ряда $0-9$, т.е. иначе "заархивировать" 8 символов по байт каждый в 3 байта. Если нужно посмотреть символы, нужное сделать обратное действие с "архивом".

[SerjeyMinsk]

(Оффтоп)

повтор сообщения

[SerjeyMinsk]

ananova в сообщении #298897 писал(а):

Википедия сообщает:

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

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

Как такое может быть?
$10^{18}$ - это всего 1 000 000 000 000 чисел.
Как может быть всех чисел 1 000 000 000 000, а простых от 0 до $10^{18}$ между тем 24 739 954 287 740 860?

[Xaositect]

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

Как такое может быть?
$10^{18}$ - это всего 1 000 000 000 000 чисел.
Как может быть всех чисел 1 000 000 000 000, а простых от 0 до $10^{18}$ между тем 24 739 954 287 740 860?

$10^{18}$ - это не 1 000 000 000 000, а 1 000 000 000 000 000 000

[SerjeyMinsk]

Xaositect в сообщении #325596 писал(а):

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

Как такое может быть?
$10^{18}$ - это всего 1 000 000 000 000 чисел.
Как может быть всех чисел 1 000 000 000 000, а простых от 0 до $10^{18}$ между тем 24 739 954 287 740 860?

$10^{18}$ - это не 1 000 000 000 000, а 1 000 000 000 000 000 000

А елы-палы. А я тут голову ломаю. Спасибо!

[age]

lorents в сообщении #325478 писал(а):

Какой будет коэффициент сжатия?

Немаленький. Думаю еще не скоро такие архиваторы появятся!

[ananova]

age в сообщении #326045 писал(а):

Думаю еще не скоро такие архиваторы появятся!

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

[Бодигрим]

Если можно пользоваться произвольным архиватором, то очевидно, что объем архива, содержащего $10^{30}$ простых чисел, может быть уложен в пару килобайт. Умный архиватор будушего, посмотрев на весь этот массив, тут же догадается, что это за последовательность и заменит ее в архиве на описание алгоритма, ее выдающего.

Что здесь противоречит законам Шеннона?

[lorents]

Бодигрим в сообщении #326250 писал(а):

Если можно пользоваться произвольным архиватором, то очевидно, что объем архива, содержащего $10^{30}$ простых чисел, может быть уложен в пару килобайт. Умный архиватор будушего, посмотрев на весь этот массив, тут же догадается, что это за последовательность и заменит ее в архиве на описание алгоритма, ее выдающего.

Что здесь противоречит законам Шеннона?

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

С другой стороны с таким подходом можно "зархивировать" бесконечное количество данных в нескольких байтах.

[ananova]

Бодигрим в сообщении #326250 писал(а):

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

Что здесь противоречит законам Шеннона?

Теперь мне понятен путь к коммунизму.

[yk2ru]

Бодигрим в сообщении #326250 писал(а):

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

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

[venco]

yk2ru в сообщении #326503 писал(а):

Бодигрим в сообщении #326250 писал(а):

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

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

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

[Бодигрим]

yk2ru в сообщении #326503 писал(а):

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

Ну да. Я правда предполагал, приличия ради, что алгоритм записывается в конструктивной форме и на некотором Тьюринг-полном языке, понятном интерпретатору разархиватора.

-- 21:18 01.06.2010 --

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

В вашем маргинальном случае распаковка чрезвычайно сложна.

Самое смешное, что не так уж и сложна. Количество операций для распаковки, т. е. для реализации какого-нибудь решета, скорее всего, отличается от длины распакованного текста (запись всех простых до $n$ занимает $O(n)$ бит) на логарифмический множитель.
Я не смог найти точную оценку количества битовых операций для решета Аткина - в Википедии не уточнено, какая именно оценка сложности указывается, с учетом многозначной арифметики или без.