Le tamis D'Atkin

Dans mon "151930920 original de la réponse à cette question , afin de les aider à mieux comprendre le Crible d'Atkin alogithm j'ai étendu le Wikipedia Crible d'Atkin (SoA) pseudo-code pour corriger certaines des lacunes dans la procédure simplifiée de "modulo 12" algorithme donné, que beaucoup trouvent difficile que par rapport à l' "modulo 60" de l'algorithme. De plus, L'algorithme original du pseudo-code de Wikipédia mène à des implémentations inefficaces; plus précisément, les plages de 'x' et les variables " y " sont chacune plus larges que nécessaire et la simplification de modulo 12 entraîne un surcroît de travail de 20%. Toutefois, comme il en a été question dans cette réponse, ce pseudo-code n'est toujours pas efficace, car les essais modulo sont toujours dans les boucles de solution quadratiques les plus internes et, par conséquent, près de la moitié de ces boucles de solution sont improductives pour les solutions qui ne passent pas les essais modulo; cela signifie qu'un programme mettant en œuvre ce pseudo-code serait probablement presque deux fois plus lent que nécessaire, même quand il n'y a pas d'accès à la mémoire vitesse d'étranglement.

l'algorithme utilisé par Atkin et Bernstein dans leur programme "primegen" pour éviter la redondance des boucles peut être mieux compris par une progression à travers les observations suivantes basées sur les tableaux " hit "dans ma réponse précédente:

1. la symétrie des tables " hit " dépend de si 'y' est impair (symétrie verticale) ou Pair (symétrie horizontale).

2. ainsi, si nous voulions que l'avance des motifs se déroule dans la direction horizontale comme indiqué ici, nous pouvons retourner l'ordre des boucles 'x' et 'y' pour les cas "3x+" et "3x-;Impair x -> Pair y" signifiant Impair 'x'.

3. maintenant, il est facile d'éliminer les zéros pour les deux tables "3x" retournées qui ont seulement cinq répétitions horizontales par une condition dans une boucle externe comme les cas où " y mod 3 = 0" plus les trois cas supplémentaires seulement pour la colonne "axe" du milieu où "y mod 5 = 0".

4. pour le dernier cas "3x -; même x - > Impair y", il est facile d'éliminer la plupart des zéros en filtrant simplement les cas où "(y + 2) mod 3 égale 0" plus les deux cas supplémentaires seulement pour la dernière ligne où "(x mod 60) égale 59 "où" (y + 2) mod 5 égale 0" (éliminations en double pour la colonne à axe vertical symétrique, qui est toujours éliminé). Bien que ces "tests y" semblent devoir se produire dans une boucle interne, comme il n'y a que cinq "hits" par côté de l'axe de symétrie verticale, ceux-ci peuvent être codés en ligne par la boucle "x".

5. les éliminations les plus difficiles sont pour la table "4x" où le patron est plus complexe: il y a cinq patrons horizontaux distincts où chacun peut être reconnu parce que le "(x mod 60) pour la première colonne" est distinct, avec un des dans le premier tableau ci-dessus, les modèles de zéros de tête ont un modulo de 5 et l'autre un modulo de 25; maintenant, les cinq modèles différents peuvent être déterminés en "inclinant" les cas comme des décalages de chaque côté de l'axe symétrique vertical pour chaque modèle.

6. L'espacement à la ligne suivante est exactement 4 × ((x + 1)2 - x2) ou 8x + 4 pour le premier tableau, (y + 2)2 - y2 ou 4y + 4 pour les deux (échangé), de nouvelles tables, et 3 × ((x + 2)2 - x2) ou 12x + 12 pour la dernière table.

7. pour tous les tableaux (maintenant) à symétrie verticale, le déport de l'axe central peut être déterminé à partir du déport de la première colonne comme (y + 16)2 - y2 ou 32y + 256 pour les rangées longues et 3 × ((x + 4)2 - x2) ou 24x + 48 pour les rangées courtes.

8. de la même manière, les décalages symétriques de part et d'autre de l'axe vertical peuvent facilement être calculés à partir du décalage de la verticale l'axe, par exemple par la paire (y + 2)2 - y2 ou 4 + 4x avec (y - 2)2 - y2 ou 4 - 4y où y est l'axe central décalé pour les cas de la rangée longue et plus et moins deux positions; le cas pour les cas de la rangée courte 'x' est similaire mais juste multiplié par trois pour l'échelle globale des valeurs "3x" 'x'.

9. les filtres ci-dessus déterminés par des conditions horizontales variables semblent briser notre objectif d'éliminer le code conditionnel dans les boucles intérieures, mais cette règle ne s'applique pas lorsque la détermination du modèle n'est pas la boucle interne, mais commence plutôt une série entière de nouvelles boucles internes à travers tous les modèles horizontalement dans le tableau pour chaque élément valide du modèle. Cela fonctionne parce que nous pouvons montrer mathématiquement que chacun de la même position équivalente dans le prochain modèle (qui a le même modulo) sont séparés comme suit: pour les avances de modèle horizontal de 30 pour les cas de la longue rangée, les modèles sont séparés par (x + 30)2 - x2 ou 60x + 900 60 × (x + 15); pour le modèle horizontal avancées par 10 pour le court rangée cas, les motifs sont séparés par 3 × ((x + 10)2 - x2) donc 60 * (x + 5). Puisque les deux ont un modulo 60 de zéro, c'est l'explication exacte de pourquoi il y a des motifs répétés du même modulo dans chaque position. Ainsi, une fois que nous trouvons l'offset pour chaque position du coin supérieur gauche, nous pouvons déterminer le modulo et l'offset pour les emplacements de départ pour les positions de modèle non-zéro et juste rouler un intérieur boucle utilisant les relations de pattern de ce point à la limite du réseau de tamis.

10. tous les incréments de colonne et de rangée ci-dessus peuvent être faits sans utiliser une opération de "diviser" en utilisant l'addition de modulo où l'algorithme garde la trace des paires de quotients et de modulo de 60 avec juste une opération de "contrôle de débordement et d'ajustement" sur la paire de modulo/quotient après chaque opération, mais le code conditionnel pour faire le "contrôle et d'ajustement" est probablement plus gourmand en ressources que la façon comme l'a écrit, pour lequel les plus modernes d'optimisation des compilateurs va générer une multiplication à l'aide de dépassement de la troncature des caractéristiques de remplacer le calcul coûteuse opération de division de la division par petits nombres, ce qui prend généralement moins de temps que la combinaison des opérations de plus le code conditionnel du "vérifier et régler la" méthode ou l'utilisation directe d'une opération de division.

11. ci-dessus les séries d'éliminations fonctionnent très bien pour une représentation en bits empaquetés des nombres premiers candidats en ce sens que chacune des 16 valeurs modulo valides peut être représentée comme un bit dans un mot de 16 bits et que l'index des mots présente les index de chaque roue modulo 60; ainsi nous pouvons avancer par incréments également divisibles par 60 en avançant simplement un nombre entier de mots de 16 bits.

Pour une utilisation en tant que non-page segmenté de l'algorithme, comme pour le code de pseudo ici, c'est suffisant pour déplacer simplement les contrôles modulo hors de la boucle la plus interne sans éliminer tous les "hit misses" pour la boucle centrale résultante, comme s'ils n'étaient pas encore maximalement efficaces en ce que la boucle centrale traite toujours les "hit misses", ce qui n'ajoute pas plus d'environ un pour cent au temps d'exécution; cependant, pour les implémentations paginées, les "coups manqués", même dans les boucles externes, peuvent ajouter beaucoup à la charge de calcul, car ces boucles sont exécutées une fois par page dans la plage des valeurs de "x". pour cette page donc il y a un facteur d'environ le logarithme de la racine carrée de la gamme tamisée plus des boucles externes pour le SoA par rapport au tamis D'Eratosthène (SoE). Une version de pseudo-code plus complexe qui représente une version (éventuellement bourrée) Non segmentée de la page de la méthode" hit optimized "Atkin et Bernstein peut alors être écrit comme suit:

// 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

en particulier, remarquez comment les boucles quadratiques les plus profondes sont très simples mais incrémentielles par une quantité variable linéairement croissante par boucle, alors que l'élimination libre des carrés premiers, qui utilise un type de progression des Eratosthènes, augmente par une quantité fixe "sqr". Ces boucles simples s'exécuteront très rapidement sur un CPU moderne, prenant environ 4 cycles d'horloge CPU par boucle si l'accès à la mémoire est assez rapide comme pour les petites gammes de tamis ou comme dans l'utilisation d'une version segmentée de page où les pages s'inscrivent dans les caches de CPU L2/L1 qui ont des temps d'accès à la mémoire d'environ cette gamme.

quand le tableau est grand comme dans beaucoup de mégaoctets, alors le temps moyen d'accès à la mémoire est susceptible de moyenne quelque chose entre 20 et plus de 100 cycles D'horloge CPU (en fonction de la vitesse de la RAM, l'efficacité de l'accès à la mémoire par le CPU, et l'efficacité de l'utilisation des caches intermédiaires) et ce sera le principal facteur limitant dans la vitesse d'exécution plutôt que l'étanchéité des boucles autre que le nombre d'opérations de bascule/cull que l'algorithme exige. Ces algorithmes particuliers, à la fois SoA et SoE, exercent une pression particulière sur l'interface mémoire pour les gros tampons en ce sens qu'ils passent à travers le tampon incrémentant par des circonférences de roue entières fois un multiplicateur à la fois et répètent pour des décalages différents plutôt que de gérer tous les "coups" de la roue dans l'ordre; ceci est dû au déplacement des tests de "coups" dans une boucle du milieu, ce qui permet d'éviter les tests de "coups" mais a pour conséquence un plus grand "saut" de tampon, avec le "saut" moyen pour le SoA plus élevé que pour le SoE. Ainsi, un l'estimation du temps d'exécution de cet algorithme sur la gamme de nombres à un milliard est d'environ 60 cycles d'horloge CPU par opération (qui sera moins d'un facteur pour L'ee en raison d'un plus petit "saut" moyenne) multiplié par le nombre d'opérations de bascule/cull (environ 260.000 pour le tamis D'Atkin) divisé par la vitesse D'horloge CPU. Par conséquent, un CPU de 3,5 GHz exécutera cet algorithme dans une plage allant jusqu'à un milliard en environ quatre secondes et la principale différence entre la vitesse d'exécution pour les non-Pagés les implémentations de la SoA et de la SoE dans ce style est la différence dans l'efficacité d'accès à la mémoire pour les gros tampons, où une SoE fortement factorisée est plus efficace d'environ un facteur de deux.

étant donné que pour les gros tampons le temps d'accès à la mémoire est le facteur de vitesse limite, il devient très important de trouver un algorithme avec un nombre minimal d'opérations. La SoA mise en œuvre par Atkin et Bernstein dans leur programme d'échantillonnage "primegen" prend environ une constante facteur d'opérations "hit" comme un rapport à la gamme tamisée, et en mettant en œuvre même une version simple d'un programme de ma première réponse, nous pouvons déterminer que ce facteur est d'environ 0,26 de la gamme premier tamisé: ce qui signifie qu'il ya environ 260.000 opérations pour une gamme tamisée d'un milliard.

pour un SoE mis en œuvre avec une grande factorisation de roue d'une roue de 210 éléments avec 48 "hits" de candidat principal par rotation (petite roue pour des nombres premiers de 2;3;5;7) en combinaison avec un pré-élimination par les nombres premiers supplémentaires de 11; 13; 17; 19, le nombre d'opérations d'élimination pour une gamme de tamis n est approximativement n fois (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 où " * "signifie multiplié par," / " signifie divisé par, M est la constante de Meissel-Mertens m ≈ 0,2614972128... si l'on corrige le nombre d'opérations découlant de l'estimation (ln n), le terme "LN n" réciproque est l'Ajustement pour l'abattage à partir du carré de la base. primes (moins que la racine carrée de la gamme n); pour n d'un milliard, le facteur par rapport à n est d'environ 0,250485568 ou environ 250 millions d'opérations de réforme pour une gamme allant jusqu'à un milliard.

c'est à peu près le même nombre d'opérations que pour la SoA et contraste avec la simple 2;3;5 roue utilisée dans le test de comparaison Atkin et Bernstein, qui a un facteur de 0.404805008 ou environ 400.000 opérations pour une gamme de tamis d'un milliard. Ce meilleur rapport pour les l'Ede factorisée signifie que les facteurs constants pour cette mise en œuvre tout à fait réalisable sont à peu près les mêmes que pour l'aos, sauf pour les différences dans les facteurs constants en raison de la complexité de la boucle.

EDIT_ADD1: pour comparaison, le code pseudo suivant est équivalent pour un SoE hautement factorisé et présélectionné écrit dans le même style que l'algorithme SOA ci-dessus:

// 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

notez combien ce code est moins complexe en dépit du fait qu'elle est plus fortement factorisée par la roue, de sorte qu'il y a moins d'opérations aériennes constantes que le code SoA, alors que la boucle d'abattage la plus interne est en fait un peu plus simple et donc (s'il y a lieu) un peu plus rapide. Remarquez également combien de boucles externes supplémentaires doivent être exécutées pour le code SoA dans Il ya un total d'à peu près le même nombre de boucles externes que la racine carrée de la gamme de tamisage pour la SoA où il ya seulement environ la gamme de tamis divisé par le logarithme naturel de la racine carrée de cette gamme boucles extérieures pour les SoE - un facteur d'environ dix fois moins pour les SoE que pour les SOA pour les criblures de gamme d'un milliard. C'est le compromis que fait la SoA: plus de boucles externes pour moins d'opérations par boucle interne avec de plus grands "sauts" de tampon entre les opérations; cependant, c'est aussi ce qui rend la SoA moins efficace par opération, en particulier pour les plus grandes gammes de tamis. END_EDIT_ADD1

As à la complexité du code pour les plus grandes gammes, celles-ci sont toujours implémentées comme des tamis segmentés par page afin d'éviter la nécessité d'avoir tout le réseau de tamis en mémoire RAM (les contraintes de mémoire limiteraient la portée) et afin de tirer profit de la localisation de la mise en cache CPU pour réduire les temps moyens d'accès à la mémoire comme discuté ci-dessus. Pour la SoE, cela peut facilement être mis en œuvre à partir d'une copie sauvegardée de la représentation des nombres premiers de la base où il y a approximativement la racine carrée de la gamme divisé par log de ce nombre racine carrée de cette gamme; pour la SoA on doit se référer à cette même représentation des nombres premiers pour l'élimination libre des carrés premiers mais aussi utiliser les valeurs des décalages de séquence plus les valeurs sauvegardées de 'x' ou 'y' (ou sauvegarder les valeurs courantes de 'x' et 'y') afin de reprendre à la page suivante offset avec un nombre total de séquences sauvegardées comme environ la racine carrée de la gamme (non divisé par le logarithme naturel de la racine n), ou alternativement nouveau 'x' / 'y' les offsets de paire peuvent être calculés pour le début de chaque nouvelle page à une hauteur de calcul considérable. La première méthode ajoute beaucoup à l'utilisation de la mémoire au-dessus de la tête, en particulier pour les implémentations multi-threadées où une copie doit être conservée pour chaque thread; la seconde n'utilise pas plus de mémoire mais utilise plus de puissance de calcul par rapport à la SoE pour ces plus grandes gammes.

page segmenté algorithmes sont également importants afin de tirer pleinement avantage de multi-core moderne CPU qui peut réduire le temps d'horloge nécessaire pour une tâche donnée par le rapport du nombre de cœurs utilisés, en particulier pour la page divisé algorithmes où chaque traitement de page peut être assignée à un thread séparé.

la façon dont l'implémentation" primesieve " SOE gère des temps de fonctionnement moyens d'environ 2,5 cycles d'horloge CPU par rapport à environ 4,5 cycles D'horloge CPU pour L'implémentation "primegen" d'Atkin et de Bernstein est par l'in-doublure extrême de la boucle cette technique peut également être appliquée à la SoA, mais ce pseudo-code en particulier n'est pas adapté pour le faire et une autre technique d'optimisation "hit rate" qui gère tous les modulos en une seule boucle (par boucle d'équation quadratique) doit être utilisée; cependant, c'est un algorithme complexe qui semble être au-delà de la portée de cette question. Il suffit de dire que les sauts en complexité jusqu'à présent ne sont rien par rapport à ce qui est nécessaire pour ajouter ce l'optimisation supplémentaire à la SoA, et même avec cela le rapport des boucles externes rend encore la SoE beaucoup plus efficace.

ainsi, alors qu'il est assez facile de mettre en œuvre un algorithme SOA naïf comme dans le pseudo-code Wikipédia original ou même en utilisant le pseudo-code SoA plus complexe comme dans ces deux réponses, il est extrêmement complexe d'écrire quelque chose qui serait en concurrence avec même "primegen" (SoA) de Bernstein, et encore moins avec le plus rapide "primesieve" (SoE), alors qu'il est assez facile de Ecrire du code qui se rapproche de la même performance que " primegen "et juste un peu plus de travail pour écrire quelque chose qui rivalise avec" primesieve " en utilisant l'algorithme SoE avec les légères modifications pour supporter la segmentation de la page.

EDIT_ADD2: pour mettre cette théorie en pratique, j'écrirais normalement un programme d'exemple pour démontrer ces principes; cependant, dans ce cas, nous avons tout ce dont nous avons vraiment besoin dans le " primegen" code source , qui est la mise en œuvre de référence par les inventeurs de la SoA. Sur ma machine (i7-2600K, 3,5 GHz) avec la taille de tampon ajustée à 32768 à partir de 8192 pour refléter ma taille de cache L1, cette "primespeed" Tamise les primes à un milliard en environ 0,365 secondes. En fait, Atkin et Bernstein ont triché un peu dans leur comparaison avec leur algorithme de tamis Eratosthenes en ce sens qu'ils n'ont attribué qu'environ quatre tampons de kilobytes à cet algorithme; en ajustant cette taille de tampon à environ la même taille (le" #define B32 1001 "à" # define B32 8008") résulte en un temps d'exécution d'environ 0,42 secondes pour" eratspeed " à environ un milliard, le laissant encore un peu plus lent. Toutefois, comme nous l'avons vu plus haut, elle fait plus de travail en effectuant environ 0,4048 milliard d'opérations de réforme, alors que la SoA n'effectue qu'environ 0,26 milliard d'opérations combinées de réforme et de réforme. En utilisant l'algorithme du pseudo-code de SoE ci-dessus pour changer Ceci est ont factorisation maximale de roue signifie que le SoE serait en fait faire un peu moins de fonctionnement que le SoA à environ 0,2505 milliards, ce qui signifie que le temps d'exécution serait réduit à environ deux tiers ou plus ou à environ 0,265 à 0,3 secondes ce qui le rend plus rapide que "primegen".

entre-temps, si l'on compare le "primespeed" au code "eratspeed", on constate que le SoE Pagé est beaucoup moins complexe que le code SoA, comme l'indique le pseudo-code ci-dessus.

bien sûr, on pourrait contrer que le SoA maintient le rapport de 0,26 fois la gamme de tamisage opérations à une gamme de tamisage aussi élevé que l'on veut tandis que le rapport SoE Monte selon les équations ci - dessus-d'environ 20% supplémentaire pour une gamme de tamisage même à cent milliards. Toutefois, compte tenu d'un léger ajustement aux deux algorithmes pour augmenter la taille du tampon et "sub slice" it pour le traiter dans les caches de L1 tranches de taille, L'État de L'économie fonctionnera comme prévu tandis que le plafond de L'État de L'économie continue d'augmenter en raison du rapport supplémentaire de boucles moyennes / internes pour L'État de L'économie par rapport à la SoE. Alors que L'entreprise D'État enregistre une augmentation des opérations d'abattage d'environ 20%, L'entreprise D'État enregistre une augmentation des boucles quadratiques de traitement d'environ 20% pour un gain net très faible, le cas échéant. Si ces optimisations ont été faites à la SoA, alors il pourrait juste rattraper la roue factorisée SoE maximale à une gamme de tamisage très large tels que dix à la dix-neuvième puissance ou plus, mais nous parlons des centaines d'années de traitement sur un ordinateur de bureau même en utilisant le multi-traitement.

SoA pourrait pratique pour le tamisage à un sous-intervalle (ie. un segment d'une page) à partir d'une très grande plage de décalage (disons dix surélevé à la puissance de vingt-deuxième), mais il ya encore ce coût de mémoire supplémentaire ou de calcul dans le traitement de toutes les valeurs de " x " et " y " qui ne sont pas nécessaires avec le SoE. END_EDIT_ADD2

comme pour ma première réponse, la comparaison dit que SoA perd à la roue fortement factorisée SoE sur presque tous les fronts, comme suit:

1. le code SoA est beaucoup plus complexe et il est plus difficile d'écrire et de maintenir, donc beaucoup plus difficile de mettre en œuvre la segmentation de page qui est si importante pour les plus grandes gammes afin de tirer profit des capacités CPU maximum comme les vitesses d'accès à la mémoire.

2. le SoA perd probablement sur les cycles D'horloge CPU d'au moins 20% en raison de code de boucle interne légèrement plus complexe et un nombre plus élevé de boucles externes.

3. la SoA a un peu plus d'opérations qu'une SoE fortement factorisée (plus grande factorisation de la roue que selon la discussion ci-dessus) pour une gamme raisonnablement grande de un à quatre milliards.

4. la SoA gagne pour de très grandes gammes en ayant un facteur d'amélioration de log (log n) que les gammes deviennent plus grandes, mais que facteur ne permettrait à la SoA de rattraper la SOE fortement factorisée à une gamme de nombre très élevé (peut-être à environ 10 soulevé à la dix-neuvième puissance) si jamais, Et alors seulement si la complexité relative reste la même, ce qui n'est pas susceptible de faire.

Donc, je dis à nouveau: " Pourquoi utiliser le Crible d'Atkin quand le Crible d'Eratosthène est mieux dans presque tous les égards et, en particulier, est moins complexe, tout en ayant moins d'une constante facteur computationnel frais généraux? " basé sur mes conclusions ici que je sens que le SoA est un tamis inférieur pour toute sorte de gamme de tamis raisonnable et ne sera probablement jamais écrire une version segmentée de la page du tamis D'Atkin, mais ont écrit beaucoup d'entre eux dans divers langages informatiques pour le tamis D'Eratosthène. Alors que le tamis D'Atkin est intéressant intellectuellement et mathématiquement, il n'est pas vraiment pratique et la comparaison D'Atkin et de Bernstein a été défectueux en trop restrictif la factorisation de roue de leur mise en œuvre du tamis D'Eratosthène utilisés dans leur comparaison pour montrer un avantage d'environ 30%, qui aurait dû être en fait environ 60% autre que pour la mise en œuvre constante des têtes du tamis d'Atkin.