Tamis d'Atkin - Sieve of Atkin

En mathématiques , le tamis d'Atkin est un algorithme moderne permettant de trouver tous les nombres premiers jusqu'à un nombre entier spécifié. Comparé à l'ancien tamis d'Ératosthène , qui délimite des multiples de nombres premiers, le tamis d'Atkin effectue un travail préliminaire puis délimite des multiples de carrés de nombres premiers, réalisant ainsi une meilleure complexité asymptotique théorique . Il a été créé en 2003 par AOL Atkin et Daniel J. Bernstein .

Algorithme

Dans l'algorithme :

• Tous les résidus sont modulo -sixty restes (diviser le nombre de 60 et de retourner le reste).
• Tous les nombres, y compris x et y , sont des entiers positifs.
• Inverser une entrée dans la liste de tamis signifie changer le marquage (prime ou non premier) pour le marquage opposé.
• Cela se traduit par des nombres avec un nombre impair de solutions à l'équation correspondante étant potentiellement premiers (premiers s'ils sont également sans carré), et des nombres avec un nombre pair de solutions étant composites.

L'algorithme :

1. Créez une liste de résultats, remplie de 2, 3 et 5.
2. Créez une liste de tamis avec une entrée pour chaque entier positif ; toutes les entrées de cette liste doivent d'abord être marquées non premières (composite).
3. Pour chaque numéro d'entrée n dans la liste de tamis, avec le reste modulo-soixante  r  :
   1. Si r vaut 1, 13, 17, 29, 37, 41, 49 ou 53, retournez l'entrée pour chaque solution possible à 4 x ²  +  y ²  =  n . Le nombre d'opérations de retournement par rapport à la plage de tamisage pour cette étape approche 4 √ tc/15 × 8/60 (le "8" dans la fraction provient des huit modulos gérés par ce quadratique et du 60 car Atkin a calculé cela sur la base d'un nombre pair de roues modulo 60), ce qui donne une fraction d'environ 0,1117010721276....
   2. Si r vaut 7, 19, 31 ou 43, retournez l'entrée pour chaque solution possible à 3 x ²  +  y ²  =  n . Le nombre d'opérations de retournement par rapport à la plage de tamisage pour cette étape approche π √ 0,12 ×4/60 (le "4" dans la fraction provient des quatre modulos gérés par ce quadratique et du 60 car Atkin l'a calculé sur la base d'un nombre pair de roues modulo 60), ce qui donne une fraction d'environ 0,072551974569....
   3. Si r vaut 11, 23, 47 ou 59, retournez l'entrée pour chaque solution possible à 3 x ²  −  y ²  =  n lorsque x  >  y . Le nombre d'opérations de retournement par rapport à la plage de tamisage pour cette étape approche √ 1,92 ln( √ 0,5 + √ 1,5 ) ×4/60 (le "4" dans la fraction provient des quatre modulos gérés par ce quadratique et le 60 car Atkin l'a calculé sur la base d'un nombre pair de roues modulo 60), ce qui donne une fraction d'environ 0,060827679704....
   4. Si r est autre chose, ignorez-le complètement.
4. Commencez par le nombre le plus bas de la liste de tamis.
5. Prenez le numéro suivant dans la liste de tamis toujours marqué premier.
6. Incluez le numéro dans la liste des résultats.
7. Mettez le nombre au carré et marquez tous les multiples de ce carré comme non premiers. Notez que les multiples qui peuvent être factorisés par 2, 3 ou 5 n'ont pas besoin d'être marqués, car ils seront ignorés dans l'énumération finale des nombres premiers.
8. Répétez les étapes quatre à sept. Le nombre total d'opérations pour ces répétitions de marquage des carrés des nombres premiers en tant que rapport de la plage de tamisage est la somme de l'inverse des nombres premiers au carré, qui se rapproche de la fonction zêta des nombres premiers (2) de 0,45224752004... moins1/2 ², 1/3 ², et 1/5 ² pour les nombres premiers qui ont été éliminés par la roue, avec le résultat multiplié par 16/60pour le rapport de coups de roue par gamme ; cela donne un rapport d'environ 0,01363637571....

En additionnant les rapports d'opérations ci-dessus, l'algorithme ci-dessus prend un rapport constant d'opérations de retournement/marquage à la plage de tamisage d'environ 0,2587171021... ; D'après une mise en œuvre réelle de l'algorithme, le rapport est d'environ 0,25 pour des plages de tamisage aussi basses que 67.

Pseudocode

Ce qui suit est un pseudocode qui combine les algorithmes d'Atkin 3.1, 3.2 et 3.3 en utilisant un ensemble combiné "s" de tous les nombres modulo 60 à l'exclusion de ceux qui sont des multiples des nombres premiers 2, 3 et 5, selon les algorithmes, pour une version simple de l' algorithme qui prend en charge le compactage de bits en option de la roue ; bien qu'il ne soit pas spécifiquement mentionné dans l'article référencé, ce pseudocode élimine certaines combinaisons évidentes de x/y impairs/pairs afin de réduire les calculs où ces calculs ne passeraient jamais les tests modulo de toute façon (c'est-à-dire produiraient des nombres pairs, ou des multiples de 3 ou 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

Ce pseudocode est écrit pour plus de clarté ; bien que certains calculs redondants aient été éliminés en contrôlant les combinaisons x/y impair/pair, il gaspille toujours près de la moitié de ses calculs quadratiques sur des boucles non productives qui ne passent pas les tests modulo de sorte qu'il ne sera pas plus rapide qu'un équivalent roue factorisée (2/3/5) tamis d'Eratosthène . Pour améliorer son efficacité, une méthode doit être conçue pour minimiser ou éliminer ces calculs non productifs.

Explication

L'algorithme ignore complètement les nombres dont le reste modulo 60 est divisible par deux, trois ou cinq, car les nombres dont le reste modulo 60 est divisible par l'un de ces trois nombres premiers sont eux-mêmes divisibles par ce nombre premier.

Tous les nombres n avec un reste modulo-soixante 1, 13, 17, 29, 37, 41, 49 ou 53 ont un reste modulo-quatre de 1. Ces nombres sont premiers si et seulement si le nombre de solutions à 4 x ² + y ² = n est impair et le nombre est sans carré (démontré par le théorème 6.1 de).

Tous les nombres n avec reste modulo-soixante 7, 19, 31 ou 43 ont un reste modulo-six de 1. Ces nombres sont premiers si et seulement si le nombre de solutions à 3 x ² + y ² = n est impair et le nombre est sans carré (démontré par le théorème 6.2 de).

Tous les nombres n avec reste modulo-soixante 11, 23, 47 ou 59 ont un reste modulo-douze de 11. Ces nombres sont premiers si et seulement si le nombre de solutions à 3 x ² − y ² = n est impair et le nombre est sans carré (prouvé par le théorème 6.3 de).

Aucun des nombres premiers potentiels n'est divisible par 2, 3 ou 5, ils ne peuvent donc pas être divisibles par leurs carrés. C'est pourquoi les chèques sans carré n'incluent pas 2 ² , 3 ² et 5 ² .

Complexité de calcul

On peut calculer que la série ci-dessus de trois opérations d'équation quadratique a chacune un nombre d'opérations qui est un rapport constant de la plage lorsque la plage tend vers l'infini; de même, les opérations d'élimination sans carré premier peuvent être décrites par la fonction zêta premier (2) avec des décalages et des facteurs constants. Il s'agit donc également d'un facteur constant de la plage lorsque la plage tend vers l'infini. Par conséquent, l'algorithme décrit ci-dessus peut calculer des nombres premiers jusqu'à N en utilisant O ( N ) opérations avec seulement O ( N ) bits de mémoire.

La version segmentée de page implémentée par les auteurs a les mêmes opérations O ( N ) mais réduit l'exigence de mémoire juste à celle requise par les nombres premiers de base en dessous de la racine carrée de la plage de O( N ^1/2 /log  N ) bits de mémoire plus un tampon de page minimal. Il s'agit de performances légèrement meilleures avec la même exigence de mémoire que le tamis segmenté de page d'Eratosthène qui utilise O( N log log  N ) opérations et les mêmes O( N ^1/2 /log  N ) bits de mémoire plus un tampon de page minimal. Cependant, un tel tamis ne surpasse pas un tamis d'Ératosthène avec une factorisation de roue pratique maximale (une combinaison d'une roue de tamisage 2/3/5/7 et de composites de pré-abattage dans les tampons de page de segment utilisant un 2/3/5/7 /11/13/17/19), qui bien qu'il ait un peu plus d'opérations que le tamis d'Atkin pour des portées très larges mais pratiques, a un facteur constant de complexité par opération d'environ trois fois en comparant le temps par opération entre les algorithmes implémentés par Bernstein en cycles d'horloge CPU par opération. Le principal problème avec le tamis segmenté de page d'Atkin est la difficulté à mettre en œuvre les séquences d'élimination « sans carré principal » en raison de l'intervalle entre les éliminations qui augmente rapidement bien au-delà de l'étendue du tampon de page ; le temps consacré à cette opération dans la mise en œuvre de Bernstein augmente rapidement jusqu'à plusieurs fois le temps consacré aux calculs d'équations quadratiques réels, ce qui signifie que la complexité linéaire de la partie qui serait autrement tout à fait négligeable devient un consommateur majeur de temps d'exécution. Ainsi, même si une implémentation optimisée peut à nouveau s'installer à une complexité temporelle O(n), ce facteur constant d'augmentation du temps par opérations signifie que le tamis d'Atkin est plus lent.

Une variation spéciale modifiée "d'énumération des points de réseau" qui n'est pas la version ci-dessus du tamis d'Atkin peut théoriquement calculer des nombres premiers jusqu'à N en utilisant O ( N / log log  N ) opérations avec N ^{1/2 + o (1)} bits de mémoire mais cette variation est rarement mise en œuvre. C'est un peu mieux en performances à un coût en mémoire très élevé par rapport à la fois à la version segmentée de page ordinaire et à une version équivalente mais rarement implémentée du tamis d'Eratosthène qui utilise les opérations O( N ) et O( N ^{1/ 2} (log log  N )/log  N ) bits de mémoire.

Pritchard a observé que pour les tamis à roues, on peut réduire la consommation de mémoire tout en préservant la complexité temporelle Big O, mais cela a généralement un coût dans un facteur constant accru pour le temps par opération en raison de la complexité supplémentaire. Par conséquent, cette version spéciale a probablement plus de valeur en tant qu'exercice intellectuel qu'un tamis principal pratique avec un temps réel réduit consacré à une large plage de tamisage pratique donnée.

Voir également

• Tamis d'Eratosthène
• Tamis Legendre
• Tamis de Sundaram
• Théorie du tamis

Les références

Liens externes

• Article sur le tamis d'Atkin et sa mise en œuvre
• Une mise en œuvre optimisée du tamis (en C )