Мне известно о том, что решето Эратосфена можно реализовать так, чтобы оно находило простые числа непрерывно без верхней границы (сегментированное решето).
У меня вопрос: можно ли таким же образом реализовать решето Аткина / Бернштейна?
Связанный вопрос: C #: как сделать Sieve of Atkin инкрементальным
Однако на соответствующий вопрос есть только один ответ: «Это невозможно для всех сит», что явно неверно.
Аткин / Бернштейн приводят сегментированную версию в Разделе 5 своей оригинальной статьи. Предположительно программа Бернштейна primegen использует этот метод.
Фактически, можно реализовать неограниченное решето Аткина (SoA), вообще не используя сегментацию, как это сделал я здесь, на F #. Обратите внимание, что это чисто функциональная версия, в которой даже не используются массивы для объединения решений квадратных уравнений и фильтра без квадратов, и поэтому она значительно медленнее, чем более императивный подход.
Оптимизация Берштейна с использованием таблиц поиска для оптимальных 32-битных диапазонов сделает код чрезвычайно сложным и непригодным для представления здесь, но было бы довольно легко адаптировать мой код F # так, чтобы последовательности начинались с установленного нижнего предела и использовались только по диапазону, чтобы реализовать сегментированную версию, и / или применяя те же методы к более императивному подходу с использованием массивов.
Обратите внимание, что даже реализация SoA Берштейном на самом деле не быстрее, чем Решето Эратосфена со всеми возможными оптимизациями согласно Сито Кима Валиша, но работает быстрее, чем эквивалентно оптимизированная версия Сита Эратосфена для выбранного диапазона чисел в соответствии с его реализацией.
EDIT_ADD: для тех, кто не хочет продираться через псевдокод Берштейна и код C, я добавляю к этому ответу метод псевдокода для использования SoA в диапазоне от LOW до HIGH. где дельта от LOW до HIGH + 1 может быть ограничена четным модулем 60, чтобы использовать оптимизацию по модулю (и потенциальную упаковку битов только для записей на колесе 2,3,5).
Это основано на возможной реализации с использованием квадратиков SoA для выражения (4 * x ^ 2 + y ^), (3 * x ^ 2 + y ^ 2) и (3 * x ^ 2 -y ^ 2) как последовательности чисел со значением x для каждой последовательности, зафиксированным на значениях от 1 до 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 четно, и наоборот. Дальнейшая оптимизация сокращает количество решений квадратных уравнений (= элементы в последовательностях), наблюдая, что шаблоны по модулю вышеупомянутых последовательностей повторяются в очень малых диапазонах x, а также повторяются в диапазонах y, равных только 30, что используется в код Берштейна, но (пока) не реализованный в моем коде F #.
Я также не включаю хорошо известные оптимизации, которые могут быть применены к выбраковке простых квадратов для использования факторизации колеса и вычислений для адреса начального сегмента, как я использую в мои реализации сегментированной SoE.
Итак, для целей вычисления адресов начальных сегментов последовательности для «4x», «3x +» и «3x-» (или с «3x +» и «3x-», объединенными, как я делаю в коде F #), и вычислив диапазоны x для каждого, как указано выше, псевдокод выглядит следующим образом:
Вычислите диапазон 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 начального элемента может быть вычислен напрямую или может быть получен с использованием справочных таблиц на основе повторяющегося характера последовательностей по модулю.
Затем каждая последовательность используется для переключения составных состояний до ВЫСОКОГО предела. Если к последовательностям добавляется дополнительная логика для перехода значений только между применимыми элементами в последовательности, дальнейшее использование условий по модулю не требуется.
Вышеупомянутое выполняется для каждой последовательности «4x», за которой следуют последовательности «3x +» и «3x-» (или объединить «3x +» и «3x-» только в один набор последовательностей «3x») до пределов x, как рассчитано. ранее или как проверено для каждого цикла.
Вот и все: при соответствующем методе разделения диапазона сита на сегменты, который лучше всего использовать в качестве фиксированных размеров, связанных с размерами кеш-памяти ЦП, для максимальной эффективности доступа к памяти, метод сегментации SoA, который использовал Бернштейн. но несколько проще по выражению, поскольку в нем упоминаются, но не сочетаются операции по модулю и битовая упаковка.
