Сито Аткина

Я пытаюсь изучить алгоритмы генерации простых чисел, и я наткнулся на Сите Аткина в Википедии. Я понимаю почти все части алгоритма, за исключением нескольких. Вот вопросы:

  1. Как образуются три квадратичных уравнения? 4x ^ 2 + y ^ 2, 3x ^ 2 + y ^ 2 и 3x ^ 2-y2
  2. Алгоритм в wikipedia говорит о модуле шестьдесят, но я не понимаю, как / где это используется в psudocode ниже.
  3. Как выглядят эти напоминания 1,5,7 и 11?

Ниже приведен псевдокод из Википедии для справки:

// arbitrary search limit limit ← 1000000 // initialize the sieve for i in [5, limit]: is_prime(i) ← false // put in candidate primes: // integers which have an odd number of // representations by certain quadratic forms for (x, y) in [1, √limit] × [1, √limit]: n ← 4x²+y² if (n ≤ limit) and (n mod 12 = 1 or n mod 12 = 5): is_prime(n) ← ¬is_prime(n) n ← 3x²+y² if (n ≤ limit) and (n mod 12 = 7): is_prime(n) ← ¬is_prime(n) n ← 3x²-y² if (x > y) and (n ≤ limit) and (n mod 12 = 11): is_prime(n) ← ¬is_prime(n) // eliminate composites by sieving for n in [5, √limit]: if is_prime(n): // n is prime, omit multiples of its square; this is // sufficient because composites which managed to get // on the list cannot be square-free is_prime(k) ← false, k ∈ {n², 2n², 3n², ..., limit} print 2, 3 for n in [5, limit]: if is_prime(n): print n 

Псевдокод сита Аткина из цитированной вами статьи Википедии содержит ответы на ваши вопросы или обсуждение статьи, для которой Уилл Несс предоставил ссылку, хотя вы не сможете собрать эту информацию вместе. Краткие ответы заключаются в следующем:

  1. Три уравнения исходят из математического доказательства Аткина, что все простые числа будут встречаться как решения одного или нескольких из этих трех уравнений с соответствующими модульными условиями для всех допустимых значений переменных «х» и «у», и на самом деле он далее доказал что истинными простыми числами будут те числа, у которых есть нечетное число решений этих трех уравнений (слева как Истина при переключении нечетное число раз из начальных условий False) с модульными условиями для каждого, исключая те числа, которые делятся на квадраты найдены простые числа, меньшие или равные квадратному корню из тестируемого числа.

  2. Истинное сито Аткина основано на наборе по модулю 60 условий; этот псевдо-код представляет собой упрощение, в котором для каждого уравнения имеется меньше диапазонов условий, используя набор по модулю 12 условий (5 × 12 = 60), однако это приводит к тому, что 20% дополнительной работы выполняется из-за введенной избыточности в этом новый набор условий. Это также является причиной того, что этот упрощенный псевдокод должен начинать свое основное сканирование в 5, а не в обычном режиме 7, и делать бесплатные квадраты свободных квадратов без начальных начальных чисел с начальной стоимостью 5 при добавленной стоимости во время выполнения в качестве факторов 5 иначе не обрабатываются должным образом. Причина этого упрощения, возможно, заключается в том, чтобы пожертвовать некоторыми дополнительными накладными расходами кода, чтобы облегчить сложность кода при проверке значений, хотя это можно сделать с помощью одного табличного поиска, тогда как дополнительные более 30% в работе из-за использования modulo 12 не может быть уменьшена.

  3. «Напоминания» (должны быть записаны в виде остатков ) найдены операторами «мод» в псевдокоде, который вы цитировали, который обозначает оператор modulo на любом компьютерном языке, который может использоваться, часто представленном символом «%» на компьютерных языках, таких как как C, Java, C #, F # и т. д. Этот оператор дает целочисленный остаток после целочисленного деления дивиденда (первый из чисел, перед «mod») на делитель (второй из чисел после символа «mod»). Причина, по которой остатки составляют всего четыре, а не 16, которые используются в полном модульном алгоритме 60, объясняется упрощением сокращения до алгоритма по модулю 12. Вы заметите, что с условиями по модулю 12 условие «4x» проходит 25, которое обычно будет устранено условиями по модулю 60, поэтому многие композиты, содержащие 25 в качестве фактора, должны быть устранены дополнительным простым 5-ти квадратным контролем , Аналогично, 55 проходит проверку «3x +» и 35 передает «3x-» чек, где они не будут для полного алгоритма по модулю 60.

Как обсуждалось в разделе «Обсуждение» в Википедии и намеченном выше, этот котируемый псевдокод никогда не намного быстрее, чем даже базовые варианты реалистичных реализаций Sieve of Eratosthenes (SoE), не говоря уже о той, которая использует ту же степень факторизации колес из-за ее неэффективности : переменные «x» и «y» не должны располагаться в пределах полного диапазона до квадратного корня из диапазона, просеянного для многих случаев (упомянутых в статье), правильное использование колеса modulo 60 восстанавливает избыточность в использование упрощения modulo 12 (как я упоминал выше), и в решениях квадратичных уравнений имеются модульные решетчатые структуры, так что условия с использованием (вычислительно медленных) модульных операций не должны проверяться с использованием алгоритма, который автоматически пропускает те решения, которые не удовлетворяли бы этим по модулю условиям в соответствии с решетчатыми узорами (упоминалось очень неясно в полной статье Аткина и Бернштейна).

Чтобы ответить на вопрос, который вы не спросили, но должен был: «Зачем использовать Сито Аткина?» ,

Основная причина, по которой используется сито Аткина (SoA), а не сито Эратосфена (SoE), заключается в том, что «знание Интернета» SOA работает быстрее. Существует две причины этого убеждения:

  1. Предполагается, что SoA быстрее, потому что асимптотическая вычислительная сложность для него меньше, чем для SoE в коэффициенте log (log n), где n – диапазон пронумерованных чисел. Практически говоря, исходя из диапазона от двух до мощности 32 (четыре миллиарда плюс) до двух к мощности 64 (около 2, за которыми следуют 19 нhive), этот коэффициент составляет шесть из пяти, равный 1,2. Это означает, что истинное значение SoE должно быть в 1,2 раза длиннее ожидаемого линейным отношением при просеивании до 64-битного диапазона чисел по сравнению с 32-битным диапазоном чисел, тогда как SoA будет иметь линейную зависимость, если бы все были идеальными , Вы можете оценить это, во-первых, это очень малый фактор для такой огромной разницы в числовых диапазонах, и, во-вторых, это преимущество справедливо только в том случае, если два алгоритма имеют одинаковую или близкую к одной и той же производительности в некотором разумном диапазоне простых чисел.

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

  2. Считается, что SoA быстрее из-за вычислительного сравнения, сделанного и опубликованного Аткиным и Бернштейном в соответствии с их статьей, связанной в статье в Википедии. Хотя работа является точной, она применима только к искусственным ограничениям, которые они применяют в алгоритме SoE, который они сравнивали: поскольку алгоритм SoA основан на факторизации по модулю 60, который представляет собой два 2,3,5 вращения факторизационных колес, они также ограничивают SoE алгоритм к той же факторизации колес. Выполняя это, SoE выполняет около 424 000 сложных операций с отбираемыми числами за один миллиард испытанного диапазона, тогда как полностью оптимизированный SoA, как было протестировано, имеет около 326 000 комбинированных операций переключения и квадратного свободного отбраковки, каждый из которых занимает примерно одно и то же время, в SoE из-за написания в том же стиле. Это означает, что SoA примерно на 30% быстрее, чем SoE для этого конкретного набора условий факсимильной обработки колес , и это точно о том, что показали сравнительный тест Atkins и Bernstein.

    Однако SoA не реагирует на дальнейшие уровни факторизации колес, поскольку уровень 2,3,5 «запекается» в алгоритме, тогда как SoE реагирует на дальнейшие уровни: используя колесо 2,3,5,7 факторизация приводит к примерно тому же количеству операций, что означает примерно такую ​​же производительность для каждого. Можно использовать даже частичный более высокий уровень факторизации колес, чем уровень 2,3,5,7, чтобы получить количество операций для SoE на 16,7% меньше, чем SoA, для пропорциональной лучшей производительности. Оптимизация, требуемая для реализации этих дополнительных уровней факторизации колес, на самом деле проще, чем сложность кода для реализации исходного оптимизированного SoA. Объем памяти для реализации этих сопоставимых реализаций с разбивкой по страницам примерно такой же, как размер буферов страниц плюс массив базовых простых чисел.

    Кроме того, обе они выиграли бы от написания в стиле «поиск состояния машины», который помог бы улучшить оптимизацию с использованием встроенного кода и разворачивания экстремальных циклов, но SoE больше походит на этот стиль, чем на SoA, из-за более простого алгоритма.

Таким образом, для сит диапазонов примерно до 32-битного числа, максимально оптимизированный SoE примерно на 20% быстрее (или больше с дальнейшей факторизации колес), чем SoA; однако SoA обладает этим преимуществом асимптотической вычислительной сложности, поэтому будет некоторый момент, когда он догоняет. Эта точка будет примерно в диапазоне, где отношение log (log n) к log (log (2 ^ 32)) или 5 равно 1,2 или диапазон примерно в 2 раза десять до девятнадцатой мощности – чрезвычайно большое число. Если оптимизированный SoA-запуск на современном настольном компьютере должен занимать около трети секунды для вычисления простых чисел в 32-битном диапазоне чисел, и если бы реализация была идеальной, так как при увеличении линейного увеличения с увеличением диапазона это потребовало бы около 45 лет, чтобы вычислить простые числа в этом диапазоне. Однако анализ простых чисел в этих высоких диапазонах часто делается небольшими кусками, для которых использование SoA было бы теоретически практичным по сравнению с SoE для очень больших сит, но с очень небольшим коэффициентом.

EDIT_ADD: На самом деле ни сегментированная страница SoE, ни SoA не работают в линейном времени для этих огромных диапазонов по сравнению с более низкими диапазонами, так как оба сталкиваются с проблемами, когда операции «переключения» и «отбраковки» теряют эффективность из-за того, что пропускать большое количество страниц за каждый прыжок; это означает, что для того, чтобы справиться с этим «перескакиванием страницы», для обоих потребуется модифицированные алгоритмы, и очень небольшое преимущество для SoA может быть полностью стерто, если есть какие-либо незначительные различия в том, как это делается. SoA имеет гораздо больше терминов в «таблицах перехода», чем SoE, примерно в обратном соотношении между количеством простых чисел, найденным до квадратного корня диапазона от этого диапазона, и это, скорее всего, добавит O (log n) как для обработки, так и для постоянного увеличения коэффициента увеличения для SoA, который имеет большее количество записей в «таблице перехода». Этот дополнительный факт в значительной степени полностью компенсирует любое преимущество SoA над SoE даже для чрезвычайно больших диапазонов. Кроме того, SoA имеет постоянные накладные расходы для более индивидуальных циклов, требуемых для многих других случаев при реализации условий для трех отдельных квадратичных уравнений плюс цикл «простых квадратов», а не только простой цикл отбора, поэтому никогда не может иметь среднее вычислительное время на операцию как SoE при полной оптимизации. END_EDIT_ADD

EDIT_ADD2: Я считаю, что большая часть путаницы в отношении Сита Аткина объясняется недостатками псевдокода из статьи в Википедии, как цитируется в вопросе, так что придумали несколько лучшую версию псевдокода, который обращается к по крайней мере, некоторые недостатки, связанные с диапазоном переменных «x» и «y», и путаница по модулю 12 по сравнению с модулем 60 следующим образом:

 limit ← 1000000000 // arbitrary search limit // Initialize the sieve for i in {7,11,13,17,19,23,29,31, 37,41,43,47,49,53,59,61,...}: is_prime(i) ← false // Put in candidate primes: // integers which have an odd number of // representations by certain quadratic forms. while n ≤ limit, n ← 4x²+y² where x ∈ {1,2,...} and y ∈ {1,3,...} // odd y's if n mod 60 ∈ {1,13,17,29,37,41,49,53}: is_prime(n) ← ¬is_prime(n) while n ≤ limit, n ← 3x²+y² where x ∈ {1,3,...} and y ∈ {2,4,...} // only odd if n mod 60 ∈ {7,19,31,43}: // x's and even y's is_prime(n) ← ¬is_prime(n) while n ≤ limit, n ← 3x²-y² where x ∈ {2,3,...} and y ∈ {x-1,x-3,...,1} //all if n mod 60 ∈ {11,23,47,59}: // even/odd odd/even combos is_prime(n) ← ¬is_prime(n) // Eliminate composites by sieving, only for those occurrences on the wheel for n² ≤ limit where n ∈ {7,11,13,17,19,23,29,31, 37,41,43,47,49,53,59,61,...}: if is_prime(n): // n is prime, omit multiples of its square; this is // sufficient because composites which managed to get // on the list cannot be square-free while c ≤ limit, c ← n² × k where k ∈ {1,7,11,13,17,19,23,29, 31,37,41,43,47,49,53,59,...}: is_prime(c) ← false output 2, 3, 5 for n ≤ limit when n ← 60 × k + x where k ∈ {0..} and x ∈ {7,11,13,17,19,23,29,31, 37,41,43,47,49,53,59,61}: if is_prime(n): output n 

Вышеизложенное кажется довольно простым и является довольно хорошим алгоритмом, за исключением того, что он все еще не быстрее, чем базовое сито Эратосфена, которое использует одно и то же колесо факторизации 2; 3; 5, потому что оно тратит почти половину своих внутренних операций переключения циклов, которые не срабатывают модульные тесты. Демонстрировать:

Ниже приводится повторяющийся рисунок 4x² + y² квалификационного по модулю 60 в диапазоне 15 значений «x» (каждое значение) по вертикали и 15 нечетных значений «y» по горизонтали; оба начинаются с одного. Обратите внимание на то, что они симметричны относительно вертикальной оси, но только 128 из 225 или 256 из 450 для полного диапазона 30 значений «x» являются действительными операциями переключения:

  0 13 29 53 0 0 53 49 53 0 0 53 29 13 0 17 0 41 0 37 17 0 1 0 17 37 0 41 0 17 37 0 1 0 0 37 0 0 0 37 0 0 1 0 37 0 13 29 53 0 0 53 49 53 0 0 53 29 13 0 41 49 0 29 1 41 29 0 29 41 1 29 0 49 41 0 0 49 13 0 0 13 0 13 0 0 13 49 0 0 17 0 41 0 37 17 0 1 0 17 37 0 41 0 17 17 0 41 0 37 17 0 1 0 17 37 0 41 0 17 0 0 49 13 0 0 13 0 13 0 0 13 49 0 0 41 49 0 29 1 41 29 0 29 41 1 29 0 49 41 0 13 29 53 0 0 53 49 53 0 0 53 29 13 0 37 0 1 0 0 37 0 0 0 37 0 0 1 0 37 17 0 41 0 37 17 0 1 0 17 37 0 41 0 17 0 13 29 53 0 0 53 49 53 0 0 53 29 13 0 1 0 0 49 0 1 49 0 49 1 0 49 0 0 1 

Ниже приведен повторяющийся шаблон 3x² + y² для квалификации по модулю 60 в диапазоне 5 нечетных значений «x» по вертикали и 15 четных значений «y» по горизонтали. Обратите внимание, что они симметричны относительно горизонтальной оси, но только 48 из 75 или 144 из 450 для полного диапазона 30 значений «x» являются действительными для переключения операций, поскольку все 144 из 450 недействительных операций с четными «x» и нечетными «y» уже устранены:

  7 19 0 7 43 0 19 19 0 43 7 0 19 7 0 31 43 0 31 7 0 43 43 0 7 31 0 43 31 0 19 31 0 19 0 0 31 31 0 0 19 0 31 19 0 31 43 0 31 7 0 43 43 0 7 31 0 43 31 0 7 19 0 7 43 0 19 19 0 43 7 0 19 7 0 

Ниже приведен повторяющийся шаблон 3x²-y² для квалификации по модулю 60 в диапазоне 5 нечетных значений «x» по вертикали и 15 четных значений «y» по горизонтали. Обратите внимание, что они симметричны относительно горизонтальной оси, но только 48 из 75 или 224 из 450 для полного диапазона 30 значений «x» являются действительными операциями переключения:

  59 47 0 59 23 0 47 47 0 23 59 0 47 59 0 23 11 0 23 47 0 11 11 0 47 23 0 11 23 0 11 59 0 11 0 0 59 59 0 0 11 0 59 11 0 23 11 0 23 47 0 11 11 0 47 23 0 11 23 0 59 47 0 59 23 0 47 47 0 23 59 0 47 59 0 

Ниже приведен повторяющийся шаблон 3x²-y² для квалификации по модулю 60 в диапазоне 5 четных значений «x» по вертикали и 15 нечетных значений «y» по горизонтали. Обратите внимание, что они симметричны относительно вертикальной оси, но только 48 из 75 или 224 из 450 для полного диапазона 30 значений «x» являются действительными операциями переключения:

  11 0 47 23 0 11 23 0 23 11 0 23 47 0 11 47 0 23 59 0 47 59 0 59 47 0 59 23 0 47 47 0 23 59 0 47 59 0 59 47 0 59 23 0 47 11 0 47 23 0 11 23 0 23 11 0 23 47 0 11 59 0 0 11 0 59 11 0 11 59 0 11 0 0 59 

Как можно определить путем проверки приведенных выше таблиц, для псевдокода, как указано выше, существует общий диапазон повторения 30 значений x (включая как коэффициенты, так и коэффициенты), которые имеют только 688 действительных операций из общего количества 1125 комбинированных операций; таким образом, он тратит почти половину своей обработки только при условном пропускании значений из-за того, что непроизводительные операции пропусков являются частью самых внутренних циклов. Существует два возможных способа устранения этой «удачной» избыточности неэффективно:

  1. Метод, описанный в статье Аткина и Бернштейна, который использует распознанные шаблоны в комбинированных модулях «х» и «у» для обработки только «по модулю» «хитов», используя тот факт, что как только один находит данный модуль по шаблону, то существует бесконечная последовательность значений при некотором модуле (равном положению битов колеса), где каждый шаблон разделяется легко вычисленным (переменным) смещением, которое имеет форму «текущая позиция плюс А, умноженная на текущее значение« x »плюс B “и” текущая позиция плюс C раз текущее значение ‘y’ плюс D “, где A, B, C и D, являются простыми константами (простое значение легко обрабатывается легко). Бернштейн использовал этот метод с дополнительной помощью многих таблиц Look Up (LUT).

  2. Метод создания общего состояния шаблона Look Up Tables (LUT) (по одному для каждой из четырех таблиц выше плюс один для младшего свободного квадрата свободного квадрата), индексированных по модулю текущими значениями ‘x’ в сочетании с модулем ‘y’ чтобы найти параметры A, B, C и D, чтобы пропустить, а не следующий шаблон, а только в следующую позицию в горизонтальной последовательности. Вероятнее всего, это более высокопроизводительный вариант, поскольку он более легко позволяет использовать экстремальный тактовый цикл для каждой операции с использованием встроенного кода разворачиваемого цикла и будет генерировать более эффективный код для больших диапазонов, когда сегментирование страниц по мере того, как скачки за цикл в среднем меньше , Это, скорее всего, приведет к тому, что тактовые циклы на петлю будут близки к высокооптимизированному сите Эратосфена, как в простых случаях , но вряд ли он достигнет такого низкого уровня из-за необходимости вычислять размеры шага переменной, а не использовать фиксированные первичные смещения для SoE.

Таким образом, есть три руководящие задачи в сокращении времени работы основного сита:

  1. Успешное сито уменьшает количество операций, которые даже «оптимизированный удар» SoA не удается по сравнению с высокооборотным факторизованным SoE примерно на 16,7% для диапазонов в несколько миллиардов.

  2. Успешное сито уменьшает циклы тактовых импульсов процессора на операцию, которые SoA терпит неудачу по сравнению с высокооптимизированным SoE, таким как primesieve, потому что его операции более сложны из-за переменных приращений, опять же, вероятно, на 20-60%. Атриум Аткина и Бернштейна (SoA) занимает около 4,5 по сравнению с примерно 2,5 тактами за операцию для primesieve (SoE) для диапазона в один миллиард для каждого, но, возможно, SoA можно было бы ускорить, заимствуя некоторые из методов оптимизации из primesieve.

  3. Успешное сито имеет достаточно низкую сложность кода, так что его можно более легко расширить до больших диапазонов, используя такие методы, как «просеивание ковша» и другие оптимизации сегментации страниц. Для этого сито Аткина терпит неудачу, поскольку оно становится экспоненциально более сложным для сегментирования страниц с большим числом диапазонов. Чрезвычайно сложно написать программу SoA, которая будет конкурировать даже с праймером Бернштейна (SoA), не говоря уже о primesieve, тогда как довольно легко написать код, который близок к той же производительности, что и primesieve.

  4. Успешное сито имеет более низкую эмпирическую сложность, которую SoA имеет выше SoE в зависимости от (log (log n), где n – верхний диапазон, который нужно просеять, но это дополнительное небольшое соотношение вряд ли будет когда-либо достаточным, чтобы составить для вышеуказанных двух верхних коэффициентов потерь, поскольку этот коэффициент становится все меньше с увеличением диапазона. END_EDIT_ADD2

Итак, ответ на вопрос «Зачем использовать Сито Аткина?» «Нет причин использовать его вообще, если SoE реализуется с максимальными оптимизациями факторизации колес до тех пор, пока просеиваемые числа не будут чрезвычайно большими (64-битный диапазон номеров и выше), а затем преимущество SoA очень мало и, возможно, невозможно реализовать при все в зависимости от очень незначительных настроек в относительной оптимизации ». ,

В качестве ответа на другое подобное сообщение «Сито Аткина» я опубликовал страницу с сегментированной версией C # для SoE, оптимизированную согласно приведенному выше: https://stackoverflow.com/a/20559687/549617 .

В моем первоначальном ответе на этот вопрос , чтобы помочь лучше понять сито Аткинского алофита, я распространил синтаксис Википедии Аткина (SoA), чтобы исправить некоторые недостатки упрощенного алгоритма «modulo 12», который многие считают запутанным по сравнению с полным алгоритмом «по модулю 60». Кроме того, оригинальный алгоритм псевдокода Wikipedia приводит к неэффективным реализациям; в частности, диапазоны переменных «x» и «y» кажутся шире, чем необходимо, и упрощение по модулю 12 приводит к дополнительному 20% избыточному результату. Однако, как обсуждалось в этом ответе, этот псевдокод по-прежнему неэффективен, поскольку модульные тесты все еще находятся в самых внутренних циклах квадратичного решения, и поэтому почти половина таких циклов решений непродуктивна для тех решений, которые не проходят модульные тесты; это означает, что программа, реализующая этот псевдокод, скорее всего, будет почти в два раза медленнее, если это необходимо, даже если нет узкого места в скорости доступа к памяти.

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

  1. Симметрия таблиц «попадание» зависит от того, является ли «y» нечетным (вертикальная симметрия) или даже (горизонтальная симметрия).

  2. Таким образом, если мы хотим, чтобы продвижение паттернов продолжалось в горизонтальном направлении, как показано там, мы можем перевернуть порядок петель «x» и «y» для «3x +» и «3x-» нечетных x -> четных y “, что означает нечетные случаи« x ».

  3. Теперь легко исключить нулевые случаи для двух перевернутых таблиц «3x», которые имеют только пять повторений по горизонтали по условию во внешнем цикле, как те случаи, когда «y mod 3 равно 0» плюс три дополнительных случая только для среднего », ось “, где” y mod 5 равно 0 “.

  4. Для последнего случая «3x-, even x -> odd y» легко исключить большую часть нhive, просто отфильтровывая те случаи, когда «(y + 2) mod 3 равно 0» плюс дополнительные два случая только для последняя строка, где «(x mod 60) равна 59», где «(y + 2) mod 5 равно 0» (дублирование исключений для столбца симметричной вертикальной оси, которое всегда устраняется). Хотя эти «y-тесты», по-видимому, должны произойти во внутреннем цикле, так как есть только пять «ударов» на сторону вертикальной оси симметрии, они могут быть встроены в цикл «x».

  5. Наиболее трудные исключения для таблицы «4x», где шаблон более сложный: существует пять различных горизонтальных шаблонов, где каждый может быть распознан, потому что «(x mod 60) для первого столбца» отличается, причем один из ведущих шаблоны нулевой строки в первой таблице выше, имеющие по модулю 5, а другой – по модулю 25; теперь пять различных моделей могут быть определены путем «вставки» случаев в качестве смещений по обе стороны от вертикальной симметричной оси для каждого шаблона.

  6. Расстояние до следующей строки равно 4 × ((x + 1) ² – x²) или 8x + 4 для первой таблицы (y + 2) ² – y² или 4y + 4 для вторых двух (замененных) новых таблиц , и 3 × ((x + 2) ² – x²) или 12x + 12 для последней таблицы.

  7. Для всех (сейчас) вертикально-симметричных таблиц смещение центральной оси может быть определено из смещения первого столбца как (y + 16) ² – y² или 32y + 256 для длинных строк и 3 × ((x + 4) ² – x²) или 24x + 48 для коротких строк.

  8. Аналогичным образом симметричные смещения по обе стороны от вертикальной оси могут быть легко вычислены по смещению вертикальной оси, например, по паре (y + 2) ² – y² или 4 + 4x с (y – 2) ² – y² или 4 – 4y где y – смещение центральной оси для длинного ряда и плюс и минус два положения; случай для коротких строк «x» аналогичен, но просто умножается на три для общего масштаба значений «3x» x.

  9. Вышеуказанные фильтры, определяемые условиями горизонтальной переменной, как представляется, нарушают нашу цель устранения условного кода во внутренних циклах, но это правило не применяется, когда определение шаблона не является внутренним циклом, а скорее запускает целую серию новых внутренних циклов во всех шаблоны горизонтально в массиве для каждого допустимого элемента шаблона. Это работает, потому что мы можем математически показать, что каждая из одинаковых эквивалентных позиций в следующем шаблоне (который имеет тот же самый модуль) разделяется следующим образом: для горизонтального шаблона вперед на 30 для длинной строки шаблоны разделяются (x + 30) ² – x² или 60x + 900, так 60 × (x + 15); для горизонтального рисунка на 10 для коротких строк, рисунки разделяются на 3 × ((x + 10) ² – x²), поэтому 60 * (x + 5). Поскольку оба имеют по модулю 60 нуля, это точное объяснение того, почему повторяются шаблоны одного и того же модуля в каждой позиции. Таким образом, как только мы найдем смещение для каждой позиции верхнего левого угла, мы можем определить по модулю и смещению для начальных позиций для ненулевых позиций шаблона и просто свернуть внутренний цикл, используя отношения шаблонов от этой точки до предела решетки решета ,

  10. Все приведенные выше приращения столбцов и строк могут быть выполнены без использования операции «разделить» с использованием дополнения по модулю, где алгоритм отслеживает пары частных и по модулю 60 с помощью только операции «переполнения и корректировки» по модулю / частному пара после каждой операции, но условный код для «проверки и настройки», скорее всего, будет более дорогостоящим по сравнению с тем, как написано, для чего большинство современных оптимизирующих компиляторов будут генерировать многократную операцию с использованием характеристик усечения переполнения для замены вычислительно дорогостоящей операции деления для деления на маленькие целые числа, что обычно занимает меньше времени, чем комбинация операций плюс условный код, необходимый для метода «проверка и настройка» или с использованием операции прямого деления.

  11. Вышеупомянутые наборы исключений работают очень хорошо для упакованного битового представления простых простых чисел, поскольку каждый из 16 действительных значений модуля может быть представлен как один бит в 16-битовом слове, а индекс слова представляет индексы каждого по модулю 60 колесо; таким образом, мы можем продвигаться на четные приращения, равномерно делимые на 60, просто продвигая целое число 16-битных слов.

Для использования в качестве несегментного сегментированного алгоритма, как здесь для псевдокода, достаточно просто переместить модульные проверки из самого внутреннего цикла, не исключая всех «промахов» для получающегося среднего цикла, как будто они все еще остаются не являются максимально эффективными в том смысле, что средний цикл все еще обрабатывает «хит-релизы», который не добавляет более чем на один процент к времени выполнения; однако для выгружаемых реализаций «пропущенные удары» даже во внешних циклах могут значительно увеличиться для вычислительных издержек, поскольку эти циклы выполняются один раз на странице в диапазоне значений «х» для этой страницы, поэтому существует коэффициент около логарифма квадратного корня просеянного диапазона больше внешних петель для SoA по сравнению с ситом эратосфенов (SoE). Версия более сложного псевдокода, который представляет (опционально битовую) версию, не подверженную сегментированию страницы «оптимизированного по удалению» метода Аткина и Бернштейна, может быть записана следующим образом:

 // arbitrary search limit limit ← 1000000000 // the set of base wheel prime candidates s ∈ {7,11,13,17,19,23,29,31, 37,41,43,47,49,53,59,61} // Initialize the sieve as an array of wheels with // enough wheels to include the representation for limit for n ← 60 * w + x where w ∈ {0,...(limit - 7) ÷ 60}, x in s: sieve(n) ← false // start with no primes. // Put in candidate primes: // integers which have an odd number of // representations by certain quadratic forms. while n ≤ limit when n ← 4x²+y² // all x's and only odd y's where x ∈ {1,...}, y ∈ {1,31,...}: // skip by pattern width in y for cb ≤ limit when midy ← y + i, cb ← n - y² + midy² where i ∈ {0,2,...28}: // middle level loop to "hit" test modulos cbd ← (cb - 7) ÷ 60, cm ← cb mod 60 if cm in {1,13,17,29,37,41,49,53}: while c ≤ limit when c ← 60 × (cbd - midy² + ((midy + 15 × j) × j)²) + cm where j {0,...}: sieve(c) ← ¬sieve(c) // toggles the affected bit while n ≤ limit when n ← 3x²+y² // only odd x's and even y's where x ∈ {1,3,...}, y ∈ {2,32,...}: // skip by pattern width in y for cb ≤ limit when midy ← y + i, cb ← n - y² + midy² where i ∈ {0,2,...28}: // middle level loop to "hit" test modulos cbd ← (cb - 7) ÷ 60, cm ← cb mod 60 if cm in {7,19,31,43}: while c ≤ limit when c ← 60 × (cbd - midy² + ((midy + 15 × j) × j)²) + cm where j {0,...}: sieve(c) ← ¬sieve(c) // toggles the affected bit while n ≤ limit when n ← 3x²-y² //even/odd & odd/even combos where x ∈ {2,3,...}, y ∈ {x-1,x-31,...,1}: // skip by pattern width in y for midy ≥ 1 and cb ≤ limit when midy ← y - i, cb ← n + y² - midy² where i ∈ {0,2,...28}: // middle level loop to "hit" test modulos cbd ← (cb - 7) ÷ 60, cm ← cb mod 60 if cm in {11,23,47,59}: while yn ≥ 1 and c ≤ limit when yn = midy - 30 * j and c ← 60 × (cbd + midy² - ((midy - 15 × j) × j)²) + cm where j {0,...}: sieve(c) ← ¬sieve(c) // toggles the affected bit // Eliminate prime squares by sieving, only for those occurrences on the wheel for sqr ≤ limit where sqr ← n², n in {7,11,13,17,19,23,29,31, 37,41,43,47,49,53,59,61,...}: if is_prime(n): // n is prime, omit multiples of its square; this is // sufficient because composites which managed to get // on the list cannot be square-free if c0 ≤ limit where c0 ← sqr × (m mod 60) where m in s: c0d ← (c0 - 7) ÷ 60, cm ← (c0 - 7) mod 60 + 7 // means cm in s while c ≤ limit for c ← 60 × (c0d + sqr × j) + cm where j ∈ {0,...}: sieve(c) ← false // cull composites of this prime square output 2, 3, 5 for n ≤ limit when n ← 60 × k + x where k ∈ {0..}, x in s: if sieve(n): output n 

In particular, notice how the innermost quadratic loops are very simple but increment by a linearly increasing variable amount per loop, whereas the prime squares free elimination, which uses a type of Eratosthenes progression, increments by a fixed amount “sqr”. These simple loops will execute quite quickly on a modern CPU, taking about 4 CPU clock cycles per loop if memory access is fast enough as for small sieve ranges or as in using a page segmented version where the pages fit within the L2/L1 CPU caches that have memory access times of about this range.

When the array is large as in many Megabytes, then the average memory access time is likely to average something between 20 and over a 100 CPU clock cycles (depending on the speed of RAM, efficiency of memory access by the CPU, and efficiency of use of intermediate caches) and this will be the main limiting factor in execution speed rather than the tightness of the loops other than the number of toggle/cull operations that the algorithm requires. These particular algorithms, both SoA and SoE, put a particular strain on the memory interface for large buffers in that they skip through the buffer incrementing by whole wheel circumferences times a multiplier at a time and repeat for a different offsets rather than handling all the “hits” of the wheel in sequence; this is due to moving the “hit” tests into a middle loop, which saves “hit” testing but has this larger buffer “jump” as a consequence, with the average “jump” for the SoA higher than for the SoE. Thus, an estimate of the execution time for this algorithm over the range of numbers to a billion is about 60 CPU clock cycles per operation (which will be less by a factor for the SoE due to a smaller average “jump”) multiplied by the number of toggle/cull operations (about 260,000 for the Sieve of Atkin) divided by the CPU clock speed. Therefore, a 3.5 GHz CPU will execute this algorithm over a range to a billion in about four seconds and the main difference between execution speed for non-paged implementations of the SoA and the SoE in this style is the difference in memory access efficiency for large buffers, where a highly wheel factorized SoE is more efficient by about a factor of two.

Given that for large buffers the memory access time is the limiting speed factor, it becomes very important to find an algorithm with a minimum number of operations. The SoA as implemented by Atkin and Bernstein in their “primegen” sample program takes about a constant factor of “hit” operations as a ratio to the range sieved, and by implementing even a simple version of a program from my first answer we can determine that this factor is about 0.26 of the prime range sieved: meaning that there are about 260,000 operations for a sieve range of a billion.

For a SoE implemented with a high wheel factorization of a 210 element wheel with 48 prime candidate “hits” per rotation (small wheel for primes of 2;3;5;7) in combination with a pre-cull by the additional primes of 11;13;17;19, the number of cull operations for a sieve range n is approximately n times (ln((ln n) / 2) + M – 1/(ln n) – 1/2 – 1/3 – 1/5 – 1/7 – 1/11 – 1/13 – 1/17 – 1/19) * 48 / 210 where ‘*’ means multiplied by, ‘/’ means divided by, M is the Meissel-Mertens constant M ≈ 0.2614972128… correcting the number of operations arising from the (ln ln n) estimate, the reciprocal “ln n” term is the adjustment for the culling starting at the square of the base primes (less than the square root of the range n); for n of one billion, the factor compared to n is about 0.250485568 or about 250 million cull operations for a range to a billion.

This is about the same number of operations as for the SoA and contrasts with the simple 2;3;5 wheel used in the Atkin and Bernstein comparison test, which has a factor of 0.404805008 or about 400,000 operations for a sieve range of one billion. This better ratio for the more highly factorized SoE means that the constant factors for this quite realizable implementation are about the same as for the SoA except for any differences in constant factors due to loop complexity.

EDIT_ADD1: For comparison, the following is equivalent pseudo code for a highly factorized and pre-culled SoE written in the same style as the above SoA algorithm:

 // arbitrary search limit limit ← 1000000000 // the set of base wheel primes r ∈ {23,29,31,37,41,43,47,53, 59,61,67,71,73,79,83, //positions + 19 89,97,101,103,107,109,113,121,127, 131,137,139,143,149,151,157,163, 167,169,173,179,181,187,191,193, 197,199,209,211,221,223,227,229} // an array of length 11 times 13 times 17 times 19 = 46189 wheels initialized // so that it doesn't contain multiples of the large wheel primes for n where n ← 210 × w + x where w ∈ {0,...46189}, x in r: // already if (n mod cp) not equal to 0 where cp ∈ {11,13,17,19}: // no 2,3,5,7 mstr(n) ← true else mstr(n) ← false // factors // Initialize the sieve as an array of the smaller wheels with // enough wheels to include the representation for limit for n where n ← 210 × w + x, w ∈ {0,...(limit - 19) ÷ 210}, x in r: sieve(n) ← mstr(n mod (210 × 46189)) // init pre-culled primes. // Eliminate composites by sieving, only for those occurrences on the // wheel using wheel factorization version of the Sieve of Eratosthenes for n² ≤ limit when n ← 210 × k + x where k ∈ {0..}, x in r if sieve(n): // n is prime, cull its multiples s ← n² - n × (x - 23) // zero'th modulo cull start position while c0 ≤ limit when c0 ← s + n × m where m in r: c0d ← (c0 - 23) ÷ 210, cm ← (c0 - 23) mod 210 + 23 //means cm in r while c ≤ limit for c ← 210 × (c0d + n × j) + cm where j ∈ {0,...}: sieve(c) ← false // cull composites of this prime output 2, 3, 5, 7, 11, 13, 17, 19, for n ≤ limit when n ← 210 × k + x where k ∈ {0..}, x in r: if sieve(n): output n 

Notice how much less complex this code is in spite of it being more highly wheel factorized so that there is less of a constant overhead of operations than the SoA code while the innermost culling loop is actually slightly simpler and therefore (if anything) likely slightly faster. Also notice how many more outer loops must be run for the SoA code in there are a total of very approximately the same number of outer loops as the square root of the sieving range for the SoA where there are only about the sieve range divided by the natural logarithm of the square root of that range outer loops for the SoE – a factor of about ten times less for the SoE compared to the SoA for sieve ranges of one billion. This is the trade-off that the SoA makes: more outer loops for less operations per inner loop with bigger buffer “jumps” between operations; however, this is also what makes the SoA less efficient per operation, especially for larger sieve ranges. END_EDIT_ADD1

As to the code complexity for larger ranges, these are always implemented as page segmented sieves in order to avoid the necessity of having the whole sieve array in RAM memory (memory constraints would limit the range) and in order to take advantage of CPU caching locality to reduce average memory access times as discussed above. For the SoE, this can easily be implemented based on a saved copy of the a base primes representation where there are approximately the square root of the range divided by log of that square root number of that range; for the SoA one needs to refer to that same base primes representation for the prime squares free elimination but as well needs to use values of sequence offsets plus saved values of ‘x’ or ‘y’ (or save the current values of both ‘x’ and ‘y’) in order to resume at the next page offset with a total number of saved sequences as about the square root of the range (not divided by natural logarithm of root n), or alternatively new ‘x’/’y’ pair offsets can be calculated for the start of each new page at a considerable computational overhead. The first method adds greatly to the memory use overhead, especially for multi-threaded implementations where a copy needs to be kept for each thread; the second doesn’t use more memory but uses more computational power as compared to the SoE for these larger ranges.

Page segmented algorithms are also important in order to take full advantage of modern multi-core CPU’s which can reduce the clock time required for a given task by the ratio of the number of cores used, especially for page divided algorithms where each page processing can be assigned to a separate thread.

The way that the “primesieve” SoE implementation manages average operation times of about 2.5 CPU clock cycles as compared to the about 4.5 CPU clock cycles for Atkin and Bernstein’s “primegen” sample implementation of the SoA is by extreme in-lining of loop unrolling with page segmentation; this technique can also be applied to the SoA but this particular pseudo code is unsuitable for doing that and an alternate technique of “hit rate” optimization that handles all of the modulos in a single loop (per quadratic equation loop) needs to be used; however, that is a complex algorithm that would seem to be beyond the scope of this question. Suffice it to say that the jumps in complexity so far are nothing as compared to what is required to add this extra optimization to the SoA, and even with that the ratio of outer loops still makes the SoE much more efficient.

Thus, while it is fairly easy to implement a naive SoA algorithm as in the original Wikipedia pseudo code or even using the more complex SoA pseudo code as in these two answers, it is extremely complex to write something that would compete with even Bernstein’s “primegen” (SoA) let alone with the faster “primesieve” (SoE), whereas it is quite easy to write code that comes close to the same performance as “primegen” and just a little more work to write something that competes with “primesieve” using the SoE algorithm with the slight modifications to support page segmentation.

EDIT_ADD2: To put this theory into practical terms, I would normally write an example program to demonstrate these principles; however, in this case we have all we really need in the “primegen” source code , which is the reference implementation by the inventors of the SoA. On my machine (i7-2600K, 3.5 GHz) with the buffer size adjusted to 32768 from 8192 to reflect my L1 cache size, this “primespeed” sieves the primes to one billion in about 0.365 seconds. In fact, Atkin and Bernstein cheated a little in their comparison to their Eratosthenes sieve algorithm in that they only assigned about four Kilobyte buffers to it; adjusting that buffer size to about the same size (the “#define B32 1001” to “#define B32 8008”) results in an execution time of about 0.42 seconds for “eratspeed” to about one billion, leaving it still slightly slower. However, as discussed above, it is doing more work in that it is doing about 0.4048 billion cull operations whereas the SoA is only doing about 0.26 billion combined toggle/cull operations. Using the algorithm from the above SoE pseudo code to change this is have maximum wheel factorization means that the SoE would actually do slightly less operation than the SoA at about 0.2505 billion, meaning the the execution time would be reduced to about two thirds or more or about 0.265 to 0.3 seconds making it faster than “primegen”.

Meanwhile, if one compares the “primespeed” to the “eratspeed” code one sees that the paged SoE is much less complex than the SoA code, just as indicated by the above pseudo code.

Of course, one could counter that the SoA maintains the ratio of 0.26 times the sieving range operations to as high a sieving range as one wants whereas the SoE ratio climbs as per the equations given above – by about an extra 20% for a sieving range even to one hundred billion. However, given a slight tweak to both algorithms to increase buffer size and “sub slice” it to process it in L1 caches sized slices, the SoE will perform as predicted whereas the overhead of the SoA continues to rise due to the extra ratio of middle/inner loops for the SoA as compared to the SoE. While the SoE has an increase in culling operations by this about 20%, the SoA has an increase in quadratic processing loops of about this same 20% for a very small net gain if any. If these optimizations were made to the SoA, then it might just catch up to the maximally wheel factorized SoE at some very large sieving range such as ten to the nineteenth power or so, but we are talking hundreds of years of processing on a desktop computer even using multi-processing.

The SoA might be practical for sieving a sub-range (ie. a single page segment) from a very large range offset (say ten raised to the twenty-second power), but there is still that cost of extra memory or computation in dealing with all those values of ‘x’ and ‘y’ that are not necessary with the SoE. END_EDIT_ADD2

Just as for my first answer, the comparison says that SoA loses to the highly wheel factorized SoE on almost all fronts, as follows:

  1. The SoA code is much more complex and it is harder to write and maintain, thus much harder to implement page segmentation which is so important for larger ranges in order to take advantage of maximum CPU capabilities as to memory access speeds.

  2. The SoA likely loses on CPU clock cycles by at least 20% due to slightly more complex inner loop code and higher numbers of outer loops.

  3. The SoA has slightly more operations as compared to a highly wheel factorized SoE (higher wheel factorization than as per the above discussion) for a reasonably large range of one to four billion.

  4. The SoA wins for very large ranges by having an improvement factor of log (log n) as ranges get bigger, but that factor would only allow the SoA to catch up to the highly wheel factorized SoE at a very high number range (perhaps at about 10 raised to the nineteenth power) if ever, and then only if the relative complexity stays the same, which it isn’t likely to do.

So I say again: ” Why use the Sieve of Atkin when the Sieve of Eratosthenes is better in almost every respect and especially is less complex while having less of a constant computational factor overhead? ” Based on my conclusions here that I feel the SoA is an inferior sieve for any kind of reasonable sieve range and will likely never write a page segmented version of the Sieve of Atkin but have written many of them in various computer languages for the Sieve of Eratosthenes. While the Sieve of Atkin is interesting intellectually and mathematically, it isn’t really practical and the Atkin and Bernstein comparison was flawed in overly restricting the wheel factorization of their implementation of the Sieve of Eratosthenes used in their comparison to show an advantage of about 30%, which should have actually been about 60% other than for the constant implementation overheads of the Sieve of Atkin.

Давайте будем гением компьютера.