Откуда исходит ограничение 10 ^ 15 в программе «Primegen» DJ Bernstein? - PullRequest
Новая
       19

Откуда исходит ограничение 10 ^ 15 в программе «Primegen» DJ Bernstein?

15 голосов
/ 27 сентября 2011

В http://cr.yp.to/primegen.html вы можете найти источники программы, которая использует сито Аткина для генерации простых чисел. Поскольку автор говорит, что может потребоваться несколько месяцев, чтобы ответить на электронное письмо, отправленное ему (я понимаю, что он действительно занятой человек!) Я отправляю этот вопрос.

На странице указано, что «primegen может генерировать простые числа до 1000000000000000». Я пытаюсь понять, почему это так. Конечно, существует ограничение до 2 ^ 64 ~ 2 * 10 ^ 19 (размер длинного целого без знака), потому что так представлены числа. Я точно знаю, что если бы существовал огромный простой промежуток (> 2 ^ 31), то печать чисел не удалась бы. Однако в этом диапазоне я думаю, что нет такого простого разрыва.

Либо автор переоценил границу (а на самом деле она составляет около 10 ^ 19), либо в исходном коде есть место, где арифметическая операция может переполниться, или что-то в этом роде.

Самое смешное, что вы МОЖЕТЕ использовать его для чисел> 10 ^ 15: 

./primes 10000000000000000 10000000000000100
10000000000000061
10000000000000069
10000000000000079
10000000000000099

и если вы верите в Wolfram Alpha, это правильно.

Некоторые факты, которые у меня были "переделаны":

  1. числа просеиваются партиями по 1920 * PRIMEGEN_WORDS = 3 932 160 чисел (см. Функцию primegen_fill в primegen_next.c)
  2. PRIMEGEN_WORDS контролирует, насколько большим будет одно просеивание - вы можете настроить его в primegen_impl.h, чтобы он соответствовал кешу вашего процессора,
  3. реализация самого сита находится в файле primegen.c - я полагаю, это правильно; то, что вы получите, это битовая маска простых чисел в pg-> buf (см. функцию primegen_fill)
  4. Битовая маска анализируется, а простые числа сохраняются в массиве pg-> p.

Не вижу точки, где может произойти переполнение.

Ответы [ 2 ]

1 голос
/ 26 октября 2011

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

0 голосов
/ 26 октября 2011

Только из алгоритма я бы сделал вывод, что верхняя граница получается из 32-битных чисел. На странице упоминается Pentium-III в качестве процессора, так что, я думаю, он очень старый и не использует 64-битную версию.

2 ^ 32 - приблизительно 10 ^ 9. Сито Аткинса (которое использует алгоритм) требует N ^ (1/2) бит (оно использует большое битовое поле). Это означает, что в 2 ^ 32 большой памяти вы можете сделать (консервативно) N около 10 ^ 15. Поскольку это число является грубой консервативной верхней границей (у вас системная и другие программы занимают память, резервируя диапазоны адресов для ввода-вывода, ...), реальная верхняя граница равна / может быть выше.

...