Сегментированное сито Аткина, возможно?

Ответ 1

Аткин/Бернштейн дают сегментированную версию в разделе 5 их оригинальной статьи . Предположительно, программа Bernstein primegen использует этот метод.

Ответ 2

На самом деле можно реализовать неограниченное сито Аткина (SoA), не использующее сегментацию вообще, как я сделал здесь, в F #. Обратите внимание, что это чистая функциональная версия, которая даже не использует массивы для объединения решений квадратичных уравнений и фильтра без квадратов и, следовательно, значительно медленнее, чем более императивный подход.

Оптимизация Berstein с использованием таблиц поиска для оптимальных 32-битных диапазонов сделает код чрезвычайно сложным и не подходит для презентации здесь, но было бы довольно легко адаптировать мой код F #, чтобы последовательности начинались с заданного нижнего предела и используются только в диапазоне для реализации сегментированной версии и/или применения тех же методов к более императивному подходу с использованием массивов.

Обратите внимание, что даже реализация Berstein в SoA не намного быстрее, чем сито Eratosthenes со всеми возможными оптимизациями по Kim Walisch primesieve но только быстрее, чем эквивалентно оптимизированная версия сита эратосфенов для выбранного диапазона чисел в соответствии с его реализацией.

EDIT_ADD: Для тех, кто не хочет пробираться через псевдокод Berstein и код C, я добавляю к этому ответу, чтобы добавить метод псевдокода для использования SoA в диапазоне от LOW to HIGH, где дельта от LOW до HIGH + 1 может быть ограничена четным модулем 60, чтобы использовать модульную (и потенциальную битную упаковку только для записей на 2,3,5 колесах).

Это основано на возможной реализации с использованием квадратов SoA (4 * x ^ 2 + y ^), (3 * x ^ 2 + y ^ 2) и (3 * x ^ 2 -y ^ 2) выражаться в виде последовательностей чисел со значением x для каждой последовательности, фиксированной значениями между одним и SQRT ((HIGH - 1)/4), SQRT ((HIGH - 1)/3) и решением квадратичной для 2 * x ^ 2 + 2 * x - HIGH - 1 = 0 для x = (SQRT (1 + 2 * (HIGH + 1)) - 1)/2 соответственно, с последовательностями, выраженными в моем коде F # в соответствии с верхним звеном. Оптимизации для последовательностей, которые используются при просеивании только для нечетных композитов, для последовательностей "4x" значения y должны быть нечетными и что для последовательностей "3x" нужно использовать нечетные значения y, когда x четно, и наоборот. Дальнейшая оптимизация уменьшает число решений квадратичных уравнений (= элементов в последовательностях), наблюдая, что модульные шаблоны по вышеприведенным последовательностям повторяются в очень малых диапазонах х, а также повторяются по диапазонам y только 30, что используется в код Berstein, но еще не реализованный в моем коде F #.

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

Итак, для целей вычисления последовательности начальных адресов сегмента для "4x" , "3x +" и "3x-" (или с "3x +" и "3x-" вместе, как и в коде F #), и вычислив диапазоны х для каждого, как указано выше, псевдокод выглядит следующим образом:

• Рассчитайте диапазон LOW - FIRST_ELEMENT, где FIRST_ELEMENT имеет самое низкое применимое значение y для каждого заданного значения x или y = x - 1 для случая последовательности "3x-" .

• Для вычисления количества элементов в этом диапазоне это сводится к вопросу о том, сколько из (y1) ^ 2 + (y2) ^ 2 + (y3) ^ 2... там где каждое число y разделено на два, чтобы получить четный или нечетный 'y по мере необходимости. Как обычно в анализе с квадратной последовательностью, мы видим, что различия между квадратами имеют постоянное возрастающее приращение, так как в дельта (9 - 1) составляет 8, дельта (25 - 9) - 16 при увеличении 8, дельта (49-25) 24 для дальнейшего увеличения 8 и т.д. так что для n элементов последний приращение для этого примера равен 8 * n. Выражая последовательность элементов, используя это, мы получаем, что это один (или любой другой, который выбирается как первый элемент) плюс восемь раз последовательность чего-то вроде (1 + 2 + 3 +... + n). Теперь применяется стандартное сокращение линейных последовательностей, где эта сумма равна (n + 1) * n/2 или n ^ 2/2 + n/2. Это мы можем решить для того, сколько n элементов есть в диапазоне, разрешив квадратное уравнение n ^ 2/2 + n/2 - range = 0 или n = (SQRT (8 * range + 1) - 1)/2.

• Теперь, если FIRST_ELEMENT + 4 * (n + 1) * n не равно LOW в качестве начального адреса, добавьте одно к n и используйте FIRST_ELEMENT + 4 * (n + 2) * (n + 1) как начальный адрес. Если вы используете дальнейшую оптимизацию, чтобы применить факторизацию колес к шаблону последовательности, то поиск табличных массивов может быть использован для поиска ближайшего значения используемого n, удовлетворяющего условиям.

• Модуль 12 или 60 исходного элемента может быть вычислен непосредственно или может быть получен с использованием таблиц поиска, основанных на повторяющемся характере последовательностей по модулю.

• Каждая последовательность затем используется для переключения составных состояний до предела HIGH. Если дополнительная логика добавляется к последовательностям для перехода значений между только применимыми элементами на последовательность, дальнейшее использование условий модуляции не требуется.

• Выше сделано для каждой последовательности "4x" , за которой следуют последовательности "3x +" и "3x-" (или объединяют "3x +" и "3x-" в один набор последовательностей "3x" ) вверх до пределов x, как было рассчитано ранее, или как проверено на каждый цикл.

И у вас есть это: с учетом соответствующего метода разделения диапазона сита на сегменты, который лучше всего использовать в качестве фиксированных размеров, которые связаны с размерами кеша процессора для лучшей эффективности доступа к памяти, метод сегментации SoA так же, как и используемый Бернштейном, но несколько более простой в выражении, поскольку он упоминает, но не сочетает операции с модулем и упаковку битов.