Сито Аткина
В математике решето Аткина — это современный алгоритм поиска всех простых чисел до заданного целого числа. По сравнению с древним решетом Эратосфена , которое отмечает кратные простым числам, решето Аткина выполняет некоторую предварительную работу, а затем отмечает кратные квадратам простых чисел, таким образом достигая лучшей теоретической асимптотической сложности . Он был создан в 2003 году АОЛ Аткиным и Дэниелом Дж. Бернштейном . [1]
Алгоритм [ править ]
В алгоритме:
- Все остатки представляют собой по модулю -шестидесяти остатки (разделите число на 60 и верните остаток).
- Все числа, включая x и y , являются целыми положительными числами.
- Перевернуть запись в ситовом списке означает изменить маркировку (простую или непростую) на противоположную маркировку.
- Это приводит к тому, что числа с нечетным количеством решений соответствующего уравнения потенциально являются простыми (простыми, если они также не содержат квадратов), а числа с четным числом решений являются составными.
Алгоритм:
- Создайте список результатов, заполненный цифрами 2, 3 и 5.
- Создайте ситчатый список с записью для каждого положительного целого числа; все записи этого списка изначально должны быть помечены как непростые (составные).
- Для каждой записи номер n в ситовом списке с остатком по модулю шестьдесят r :
- Если r равно 1, 13, 17, 29, 37, 41, 49 или 53, переверните запись для каждого возможного решения на 4 x 2 + и 2 = п . Число операций переворота как отношение к диапазону просеивания для этого шага приближается 4 √ π / 15 [1] × 8/60 («8» в дроби получается из восьми модулей, обрабатываемых этим квадратичным числом, и 60 , потому что Аткин рассчитал это на основе четного числа колес по модулю 60), что дает дробь около 0,1117010721276....
- Если r равно 7, 19, 31 или 43, переверните запись для каждого возможного решения на 3 x 2 + и 2 = п . Число операций переворота как отношение к диапазону просеивания на этом этапе приближается к π √ 0,12. [1] × 4/60 , и 60 , («4» в дроби происходит от четырех модулей, обрабатываемых этим квадратичным числом потому что Аткин рассчитал это на основе четного числа колес по модулю 60), что дает дробь около 0,072551974569....
- Если r равно 11, 23, 47 или 59, переверните запись для каждого возможного решения на 3 x 2 − и 2 = n, когда x > y . Число операций переворачивания по отношению к диапазону просеивания на этом этапе приближается к √ 1,92 ln( √ 0,5 + √ 1,5 ). [1] × 4/60 , и 60 , («4» в дроби происходит от четырех модулей, обрабатываемых этим квадратичным числом потому что Аткин рассчитал это на основе четного числа колес по модулю 60), что дает дробь примерно 0,060827679704....
- Если r — это что-то другое, полностью игнорируйте это.
- Начните с наименьшего номера в списке сит.
- Возьмите следующее число в списке сит, которое все еще отмечено штрихом.
- Включите номер в список результатов.
- Возведите число в квадрат и отметьте все кратные этому квадрату как непростые. Обратите внимание, что кратные, которые можно разложить на 2, 3 или 5, отмечать не нужно, поскольку они будут игнорироваться при окончательном перечислении простых чисел.
- Повторите шаги с четвертого по седьмой. Общее количество операций для этих повторений маркировки квадратов простых чисел как отношения диапазона просеивания представляет собой сумму, обратную квадрату простых чисел, которая приближается к дзета -функции простых чисел (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. [1] используя комбинированный набор «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 + и 2 = n нечетно и число не содержит квадратов (доказано в теореме 6.1 из [1] ).
Все числа n с остатком по модулю шестьдесят 7, 19, 31 или 43 имеют остаток по модулю шесть, равный 1. Эти числа являются простыми тогда и только тогда, когда количество решений уравнения 3 x 2 + и 2 = n нечетно и число не содержит квадратов (доказано в теореме 6.2 из [1] ).
Все числа n с остатком по модулю шестьдесят 11, 23, 47 или 59 имеют остаток по модулю двенадцать, равный 11. Эти числа являются простыми тогда и только тогда, когда количество решений уравнения 3 x 2 − и 2 = n нечетно и число не содержит квадратов (доказано в теореме 6.3 из [1] ).
Ни одно из потенциальных простых чисел не делится на 2, 3 или 5, поэтому они не делятся на свои квадраты. Вот почему проверки без квадратов не включают 2 2 , 3 2 , и 5 2 .
Вычислительная сложность [ править ]
Это можно вычислить [1] что каждая из приведенных выше серий из трех операций с квадратными уравнениями имеет количество операций, которое является постоянным отношением диапазона при стремлении диапазона к бесконечности; кроме того, операции по отбраковке простых чисел без простых квадратов могут быть описаны простой дзета-функцией (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] плюс минимальный страничный буфер. Однако такое решето не превосходит решето Эратосфена с максимально практичной факторизацией колес (комбинация просеивающего колеса 2/3/5/7 и предварительного отбора композитов в буферах страниц сегмента с использованием 2/3/5/7). /11/13/17/19), который, хотя и имеет немного больше операций, чем Решето Аткина для очень больших, но практичных диапазонов, имеет постоянный коэффициент меньшей сложности на операцию примерно в три раза при сравнении времени на операцию между алгоритмы, реализованные Бернштейном, в тактовых циклах ЦП на операцию. Основная проблема с сегментированным по страницам ситом Аткина заключается в сложности реализации последовательностей отбраковки «без простых квадратов» из-за того, что интервал между отбраковками быстро растет далеко за пределы диапазона страничного буфера; время, затрачиваемое на эту операцию в реализации Бернштейна, быстро возрастает во много раз по сравнению со временем, затрачиваемым на фактические вычисления квадратных уравнений, а это означает, что линейная сложность части, которая в противном случае была бы совершенно незначительной, становится основным потребителем времени выполнения. Таким образом, даже несмотря на то, что оптимизированная реализация может снова достичь временной сложности O(n), этот постоянный фактор увеличения времени на операцию означает, что решето Аткина работает медленнее.
Специальный модифицированный вариант «перечисления точек решетки» , который не является вышеупомянутой версией Решета Аткина, теоретически может вычислять простые числа до N, используя O ( N /log log N ) операций с N 1/2 + о(1) кусочки памяти [1] но этот вариант реализуется редко. Это немного лучше по производительности при очень высоких затратах памяти по сравнению как с обычной версией с сегментированием страниц, так и с эквивалентной, но редко реализуемой версией решета Эратосфена, которая использует операции O( N ) и O( N 1/2 (log log N )/log N ) бит памяти. [3] [4] [5]
Притчард заметил, что для колесных сит можно уменьшить потребление памяти, сохранив при этом временную сложность Большого О, но обычно за это приходится платить увеличением постоянного коэффициента времени на операцию из-за дополнительной сложности. Таким образом, эта специальная версия, вероятно, более ценна как интеллектуальное упражнение, чем практическое основное сито с уменьшенными затратами реального времени для заданного большого практического диапазона просеивания.
См. также [ править ]
Ссылки [ править ]
- ↑ Перейти обратно: Перейти обратно: а б с д и ж г час я дж АОЛ Аткин, Д. Д. Бернштейн, Простые сита с использованием бинарных квадратичных форм , Матем. Комп. 73 (2004), 1023-1030. [1]
- ^ Причард, Пол, «Линейные сита простых чисел: генеалогическое древо», Sci. Вычислить. Программирование 9 :1 (1987), стр. 17–35.
- ^ Пол Притчард, Сублинейное аддитивное сито для поиска простых чисел, Сообщения ACM 24 (1981), 18–23. МИСТЕР 600730
- ^ Пол Причард, Объяснение колесного сита, Acta Informatica 17 (1982), 477–485. МИСТЕР 685983
- ^ Пол Причард, Быстрые компактные сита простых чисел (среди прочих), Journal of Algorithms 4 (1983), 332–344. МИСТЕР 729229