Сито Аткина - Sieve of Atkin

В математике , то решето Аткин современный алгоритм нахождения всех простых чисел до заданного целого числа. По сравнению с древним ситом Эратосфена , которое отмечает кратные числа простых чисел, сито Аткина выполняет некоторую предварительную работу, а затем отмечает кратные квадраты простых чисел, таким образом достигая лучшей теоретической асимптотической сложности . Он был создан в 2003 году AOL Atkin и Daniel J. Bernstein .

Алгоритм

В алгоритме:

  • Все остатки являются по модулю -sixty остатков (разделить число на 60 и возвращают остаток).
  • Все числа, включая x и y , являются целыми положительными числами.
  • Переворачивание записи в списке сита означает изменение маркировки (первичная или непростая) на противоположную.
  • Это приводит к тому, что числа с нечетным числом решений соответствующего уравнения являются потенциально простыми (простыми, если они также свободны от квадратов), а числа с четным числом решений являются составными.

Алгоритм:

  1. Создайте список результатов, заполненный цифрами 2, 3 и 5.
  2. Создайте решетчатый список с записью для каждого положительного целого числа; все записи этого списка изначально должны быть помечены как непростые (составные).
  3. Для каждой записи номер n в сетчатом списке с остатком r по модулю шестьдесят   :
    1. Если r равно 1, 13, 17, 29, 37, 41, 49 или 53, переверните запись для каждого возможного решения на 4 x 2  +  y 2  =  n . Количество операций переворачивания в соотношении к диапазону просеивания на этом этапе приближается к 4 √ π/15 × 8/60 («8» в дроби происходит от восьми модулей по модулю, обрабатываемых этой квадратичной системой, и от 60, потому что Аткин вычислил это на основе четного числа колес по модулю 60), что дает дробную часть примерно 0,1117010721276 ....
    2. Если r равно 7, 19, 31 или 43, переверните запись для каждого возможного решения на 3 x 2  +  y 2  =  n . Количество операций переворачивания как отношение к диапазону просеивания на этом этапе приближается к π √ 0,12 ×4/60 («4» в дроби происходит от четырех модулей, обрабатываемых этим квадратичным, и 60, потому что Аткин вычислил это на основе четного числа колес по модулю 60), что дает дробь примерно 0,072551974569 ....
    3. Если r равно 11, 23, 47 или 59, переверните запись для каждого возможного решения на 3 x 2  -  y 2  =  n, когда x  >  y . Число операций переворачивания как отношение к диапазону просеивания для этого этапа приближается к √ 1,92 ln ( √ 0,5 + √ 1,5 ) ×4/60 («4» в дроби происходит от четырех модулей, обрабатываемых этим квадратичным, и 60, потому что Аткин вычислил это на основе четного числа колес по модулю 60), что дает дробь примерно 0,060827679704 ....
    4. Если r - это что-то еще, полностью игнорируйте его.
  4. Начните с наименьшего числа в списке сита.
  5. Возьмите следующее число в списке сита, все еще отмеченное штрихом.
  6. Включите номер в список результатов.
  7. Возведите это число в квадрат и пометьте все кратные этого квадрата непростыми. Обратите внимание, что кратные, которые могут быть разложены на 2, 3 или 5, не нужно отмечать, так как они будут проигнорированы при окончательном перечислении простых чисел.
  8. Повторите шаги с четвертого по седьмой. Общее количество операций для этих повторений маркировки квадратов простых чисел как отношения диапазона просеивания представляет собой сумму, обратную квадрату простых чисел, которая приближается к простой дзета-функции (2), равной 0,45224752004 ... минус1/2 2, 1/3 2, а также 1/5 2 для тех простых чисел, которые были удалены колесом, с результатом, умноженным на 16/60по соотношению попаданий колес на дальность; это приводит к соотношению примерно 0,01363637571 ....

Суммируя вышеупомянутые соотношения операций вместе, вышеупомянутый алгоритм принимает постоянное отношение операций переворачивания / маркировки к диапазону просеивания примерно 0,2587171021 ...; Исходя из фактической реализации алгоритма, соотношение составляет около 0,25 для диапазонов рассева всего лишь 67.

Псевдокод

Ниже приведен псевдокод, который объединяет алгоритмы Аткина 3.1, 3.2 и 3.3 с использованием объединенного набора «s» всех чисел по модулю 60, за исключением тех, которые кратны простым числам 2, 3 и 5, согласно алгоритмам, для простая версия алгоритма , поддерживающая необязательную битовую упаковку колеса; хотя конкретно не упоминается в упомянутой статье, этот псевдокод устраняет некоторые очевидные комбинации нечетных / четных x / y, чтобы уменьшить количество вычислений, при которых эти вычисления в любом случае никогда не пройдут тесты по модулю (т. е. будут давать четные числа или кратные 3 или 5 ): 

limit ← 1000000000        // arbitrary search limit

// set of wheel "hit" positions for a 2/3/5 wheel rolled twice as per the Atkin algorithm
s ← {1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59}

// Initialize the sieve with enough wheels to include limit:
for n ← 60 × w + x where w ∈ {0,1,...,limit ÷ 60}, x ∈ s:
    is_prime(n) ← false

// Put in candidate primes:
//   integers which have an odd number of
//   representations by certain quadratic forms.
// Algorithm step 3.1:
for n ≤ limit, n ← 4x²+y² where x ∈ {1,2,...} and y ∈ {1,3,...} // all x's odd y's
    if n mod 60 ∈ {1,13,17,29,37,41,49,53}:
        is_prime(n) ← ¬is_prime(n)   // toggle state
// Algorithm step 3.2:
for n ≤ limit, n ← 3x²+y² where x ∈ {1,3,...} and y ∈ {2,4,...} // only odd x's
    if n mod 60 ∈ {7,19,31,43}:                                 // and even y's
        is_prime(n) ← ¬is_prime(n)   // toggle state
// Algorithm step 3.3:
for n ≤ limit, n ← 3x²-y² where x ∈ {2,3,...} and y ∈ {x-1,x-3,...,1} //all even/odd
    if n mod 60 ∈ {11,23,47,59}:                                   // odd/even combos
        is_prime(n) ← ¬is_prime(n)   // toggle state

// Eliminate composites by sieving, only for those occurrences on the wheel:
for n² ≤ limit, n ← 60 × w + x where w ∈ {0,1,...}, x ∈ s, n ≥ 7:
    if is_prime(n):
        // n is prime, omit multiples of its square; this is sufficient 
        // because square-free composites can't get on this list
        for c ≤ limit, c ← n² × (60 × w + x) where w ∈ {0,1,...}, x ∈ s:
            is_prime(c) ← false

// one sweep to produce a sequential list of primes up to limit:
output 2, 3, 5
for 7 ≤ n ≤ limit, n ← 60 × w + x where w ∈ {0,1,...}, x ∈ s:
    if is_prime(n): output n

Этот псевдокод написан для ясности; хотя некоторые избыточные вычисления были устранены путем управления комбинациями нечетных / четных x / y, он по-прежнему тратит почти половину своих квадратичных вычислений на непродуктивные циклы, которые не проходят тесты по модулю, так что он не будет быстрее, чем эквивалентный колесо факторизованное (2/3/5) сита Эратосфена . Чтобы повысить его эффективность, необходимо разработать метод, сводящий к минимуму или устраняющий эти непродуктивные вычисления.

Объяснение

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

Все числа n с остатком по модулю шестьдесят 1, 13, 17, 29, 37, 41, 49 или 53 имеют остаток по модулю четыре от 1. Эти числа являются простыми тогда и только тогда, когда количество решений для 4 x 2 + y 2 = n нечетно, а число бесквадратное (доказано как теорема 6.1).

Все числа n с остатком 7, 19, 31 или 43 по модулю шестьдесят имеют остаток по модулю шесть, равный 1. Эти числа являются простыми тогда и только тогда, когда количество решений 3 x 2 + y 2 = n нечетно и число бесквадратное (доказано как теорема 6.2).

Все числа n с остатком по модулю шестьдесят 11, 23, 47 или 59 имеют остаток по модулю двенадцать, равный 11. Эти числа являются простыми тогда и только тогда, когда количество решений 3 x 2 - y 2 = n нечетно и число бесквадратное (доказано как теорема 6.3).

Ни одно из потенциальных простых чисел не делится на 2, 3 или 5, поэтому они не могут делиться на свои квадраты. Вот почему проверки без квадратов не включают 2 2 , 3 2 и 5 2 .

Вычислительная сложность

Можно вычислить, что каждая из трех вышеуказанных операций с квадратным уравнением имеет ряд операций, которые являются постоянным соотношением диапазона, когда диапазон стремится к бесконечности; кроме того, операции выборки без простых квадратов могут быть описаны простой дзета-функцией (2) с постоянными смещениями и множителями, поэтому она также является постоянным множителем диапазона, когда диапазон стремится к бесконечности. Следовательно, описанный выше алгоритм может вычислять простые числа до N, используя O ( N ) операций только с O ( N ) битами памяти.

Страничная сегментированная версия, реализованная авторами, имеет те же операции O ( N ), но снижает требования к памяти до уровня, необходимого для базовых простых чисел ниже квадратного корня из диапазона O ( N 1/2 / log  N ) бит памяти. плюс минимальный буфер страницы. Это немного лучшая производительность при тех же требованиях к памяти, что и у сегментированного страничного сита Эратосфена, которое использует O ( N log log  N ) операций и те же O ( N 1/2 / log  N ) бит памяти плюс минимальный буфер страницы. Однако такое сито не превосходит сито Эратосфена с максимальной практичной факторизацией колеса (комбинация просеивающего колеса 2/3/5/7 и предварительной отбраковки композитов в буферах страницы сегментов с использованием 2/3/5/7 / 11/13/17/19), который, хотя и имеет немного больше операций, чем Сито Аткина для очень больших, но практичных диапазонов, имеет постоянный коэффициент меньшей сложности на операцию примерно в три раза при сравнении времени на операцию между алгоритмы, реализованные Бернштейном в тактовых циклах ЦП на операцию. Основная проблема со страничным сегментированным решетом Аткина - сложность в реализации последовательностей отбраковки «без простых квадратов» из-за того, что интервал между отбраковками быстро растет далеко за пределы диапазона буфера страницы; время, затрачиваемое на эту операцию в реализации Бернштейна, быстро увеличивается во много раз по сравнению со временем, затрачиваемым на фактические вычисления квадратного уравнения, а это означает, что линейная сложность той части, которая в противном случае была бы весьма незначительной, становится основным потребителем времени выполнения. Таким образом, даже несмотря на то, что оптимизированная реализация может снова достичь временной сложности O (n), этот постоянный коэффициент увеличения времени на одну операцию означает, что Сито Аткина работает медленнее.

Специальная модифицированная вариация «перечисления точек решетки», которая не является приведенной выше версией Решета Аткина, теоретически может вычислять простые числа до N, используя O ( N / log log  N ) операций с N 1/2 + o (1) битами памяти. но этот вариант реализуется редко. Это немного лучше по производительности при очень высокой стоимости памяти по сравнению как с обычной страничной сегментированной версией, так и с эквивалентной, но редко реализуемой версией решета Эратосфена, которая использует O ( N ) операций и O ( N 1 / 2 (log log  N ) / log  N ) бит памяти.

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

Смотрите также

использованная литература

  1. ^ a b c d e f g h i j A.OL Atkin, DJ Bernstein, Простые сита с использованием бинарных квадратичных форм , Math. Комп. 73 (2004), 1023-1030. [1]
  2. ^ Причард, Пол, "Линейные сита простых чисел: генеалогическое древо", Sci. Comput. Программирование 9 : 1 (1987), стр. 17–35.
  3. ^ Пол Притчард, Сублинейное аддитивное решето для нахождения простых чисел, Сообщения ACM 24 (1981), 18–23. Руководство по ремонту 600730
  4. ↑ Пол Причард, Объяснение колесного сита, Acta Informatica 17 (1982), 477–485. Руководство по ремонту 685983
  5. ^ Пол Притчард, Быстрые компактные сита для простых чисел (среди прочих), Журнал алгоритмов 4 (1983), 332–344. Руководство по ремонту 729229

внешние ссылки