Где ограничение 10 ^ 15 в D.J. Исходная программа Бернштейна?

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

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

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

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

./primes 10000000000000000 10000000000000100
10000000000000061
10000000000000069
10000000000000079
10000000000000099

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

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

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

Я не вижу смысла, когда может произойти переполнение.

Ответы

Ответ 1

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

Ответ 2

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

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