Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Алгоритм [ править ]

В алгоритме:

  • Все остатки являются по модулю -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[1] ×8/60 («8» в дроби происходит от восьми модулей по модулю, обрабатываемых этой квадратичной системой, и 60, потому что Аткин вычислил это на основе четного числа колес по модулю 60), что дает дробную часть примерно 0,1117010721276 ....
    2. Если r равно 7, 19, 31 или 43, переверните запись для каждого возможного решения на 3 x 2  +  y 2  =  n . Количество операций переворачивания как отношение к диапазону просеивания для этого шага приближается к π √ 0,12 [1] ×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 ) [1] ×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 [1] с использованием объединенного набора «s» всех чисел по модулю 60, за исключением тех, которые кратны простым числам 2, 3 и 5, в соответствии с алгоритмы для простой версии алгоритма, который поддерживает дополнительную битовую упаковку колеса; хотя конкретно не упоминается в упомянутой статье, этот псевдокод устраняет некоторые очевидные комбинации нечетных / четных x / y, чтобы сократить вычисления, когда эти вычисления все равно никогда не пройдут тесты по модулю (то есть будут давать четные числа или кратные 3 или 5 ):

limit  ←  1000000000  // произвольный лимит поиска// набор позиций "попадания" колеса для колеса 2/3/5, прокрученного дважды в соответствии с алгоритмом Аткина s  ←  { 1 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 49 , 53 , 59 }// Инициализируем решето с достаточным количеством колес для включения limit: для  n  ←  60  ×  w  +  x,  где  w  ∈  { 0 , 1 , ..., limit  ÷  60 },  x  ∈  s :  is_prime ( n )  ←  false// Вставьте в число кандидатов простые числа: // целые числа, которые имеют нечетное количество // представлений определенными квадратичными формами. // Шаг алгоритма 3.1: для  n  ≤  limit ,  n  ←  4 x² + y²,  где  x  ∈  { 1 , 2 , ...}  и  y  ∈  { 1 , 3 , ...}  // все x нечетные y,  если  n  mod  60  ∈  { 1 , 13 , 17 , 29 , 37 ,41 , 49 , 53 } :  is_prime ( n )  ←  ¬ is_prime ( n )  // переключить состояние // Шаг алгоритма 3.2: для  n  ≤  limit ,  n  ←  3 x² + y²,  где  x  ∈  { 1 , 3 , ...}  and  y  ∈  { 2 , 4 , ...}  // только нечетные x,  если  n  mod  60  ∈  { 7, 19 , 31 , 43 } :  // и даже y  is_prime ( n )  ←  ¬ is_prime ( n )  // переключить состояние // Шаг алгоритма 3.3: для  n  ≤  limit ,  n  ←  3 x² - y²,  где  x  ∈  { 2 , 3 , ...}  и  y  ∈  { x -1 , x -3 , ..., 1 }  // все четные / нечетные,  если n  mod  60  ∈  { 11 , 23 , 47 , 59 } :  // нечетные / четные комбинации  is_prime ( n )  ←  ¬ is_prime ( n )  // переключить состояние// Удаляем композиты путем просеивания, только для тех вхождений на колесе: для  n²  ≤  limit ,  n  ←  60  ×  w  +  x,  где  w  ∈  { 0 , 1 , ...},  x  ∈  s ,  n  ≥  7 :  if  is_prime ( n ) :  // n простое число, не кратные его квадрату;  //  этого достаточно, потому что композиты без квадратов не могут попасть в этот список при  c  ≤  limit ,  c  ←  n² ×  ( 60  ×  w  +  x ),  где  w  ∈  { 0 , 1 , ...},  x  ∈  s :  is_prime ( c )  ←  false// одна обработка для получения последовательного списка простых чисел до предела: вывод  2 ,  3 ,  5 для  7  ≤  n  ≤  limit ,  n  ←  60  ×  w  +  x,  где  w  ∈  { 0 , 1 , ...},  x  ∈  s :  if  is_prime ( n ) :  вывод  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 из [1] ).

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

Все числа n с остатком по модулю шестьдесят 11, 23, 47 или 59 имеют остаток по модулю двенадцать, равный 11. Эти числа являются простыми тогда и только тогда, когда количество решений 3 x 2 - y 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 + o (1) битами памяти. [1], но этот вариант применяется редко. Это немного лучше по производительности при очень высокой стоимости памяти по сравнению как с обычной страничной сегментированной версией, так и с эквивалентной, но редко реализуемой версией решета Эратосфена, которая использует O ( N ) операций и O ( N 1 / 2 (журнал журнал  N ) / журнал  N) бит памяти. [3] [4] [5]

Притчард заметил, что для колесных сит можно уменьшить потребление памяти при сохранении временной сложности 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

Внешние ссылки [ править ]

  • Статья о Сите Аткина и реализации
  • Оптимизированная реализация сита (на C )