Un Crible d'Atkin bizarre

Soyez le premier à donner votre avis sur cette source.

Vue 2 045 fois - Téléchargée 342 fois

Description

A la fin de l'article Nombres premiers: Crible d'Atkin , j'avais exprimé ma déception en ce qui concerne la rapidité de l'algorithme.
Finalement, je me suis décidé à le réétudier, en me basant, comme dans le "crible des multiplications", sur des "prints" intermédiaires. Il devient alors évident qu'on peut encore faire bien des améliorations !
Ces "prints" peuvent être obtenus avec AtkinPrint.html ou, avec mx=10000, directement dans AtkinPrint_10000.txt.

Utilisez Atkin.html pour tester et mesurer l'ensemble des codes explorés.
Si le temps d'attente dépasse une ou deux minutes, diminuez le mx maximal dans la function Test():   for (var mx=10; mx<=100000000; mx*=10) {...}.
Mes propres mesures se trouvent à la fin de ce texte.

Voir aussi l'article Atkin bizarre C/C++.
 
 

Atkin3.js


Nous partons du code suivant correspondant à Atkin2.js:
function Atkin2(mx) {
  var i,n,nn,x,y,r=Math.floor(Math.sqrt(mx));
  var sv=[false,false,true,true]; // for 0,1,2,3
  for (i=4; i<=mx; ++i) sv[i]=false;
  for (x=1; x<=r; ++x) { // Boucle principale
    var xx=x*x,xx3=xx*3,xx4=xx3+xx;
    for (y=1; y<x; ++y) // Boucle A
      if ((n=xx3-y*y)<=mx && (n%12==11)) sv[n]=!sv[n];
    if (xx3<mx)
      for (y=1; y<=r; ++y) // Boucle B
        if ((n=xx3+y*y)<=mx && (n%12==7)) sv[n]=!sv[n];
    if (xx4<mx)
      for (y=1; y<=r; ++y) // Boucle C
        if ((n=xx4+y*y)<=mx && (n%12==1||n%12==5)) sv[n]=!sv[n];
  }
  for (n=5; n<=r; ++n)
    if (sv[n]) for (nn=n*n,i=nn; i<=mx; i+=nn) sv[i]=false;
  for (i=0,n=0; i<=mx; ++i)
    if (sv[i]) ++n; // i is prime
  return n;
}
Et nous introduisons quelques "prints" intermédiaires en utilisant les variables sA, sB et sC (voir AtkinPrint.html).

On constate alors que les 3 boucles tournent souvent "à vide".
Séparons les complètement pour pouvoir bien y ajuster les limites et éviter les traitements inutiles:
Boucle A:
x >= 2, 1 <= y < x, 3·x²-y² <= mx; avec y = x-1, on a 3·x²-(x-1)² <= mx ou 2·x²+2·x-(mx+1) <= 0
Nous pourrions résoudre cette équation de second degré, Mais nous limiterons simplement les x par sqrt(mx/2).
Inversons le sens de parcours de la boucle while et remarquons que le plus grand y ainsi que sa décrémentation dépendent de x%3.
Boucle B:
3·x·x + y·y <= mx ==> x <= sqrt(mx/3).
x est impair, y commence par 2 et augmente alternativement par 2 et 4.
Boucle C:
4·x·x + y·y <= mx ==> x <= sqrt(mx/4).
y commence à 1 et i augmente selon x%3 de 2 ou de 4,2 alternativement.

Finalement, nous avons réussi à éliminer, dans les boucles while, les instructions avec %12 (modulo 12) qui sont assez gourmand.
function Atkin3(mx) {
  var d,i,n,nn,r,x,xx,y,z=Math.sqrt(mx);
  var sv=[false,false,true,true]; // for 0,1,2,3
  for (i=4; i<=mx; ++i) sv[i]=false;
  r=Math.floor(z*0.7071067812); // z*0.7071067812 = sqrt(mx/2)
  for (x=2; x<r; ++x) { // Boucle A
    xx=3*x*x; y=(x%3==1)?x-3:x-1; d=(x%3)?4:2;
    while ((y>0)&&((n=xx-y*y)<=mx)) {sv[n]=!sv[n]; y-=(d=6-d);}
  }
  r=Math.floor(z*0.5773502692); // z*0.5773502692 = sqrt(mx/3)
  for (x=1; x<=r; x+=2) { // Boucle B
    xx=3*x*x; y=2; d=4;
    while ((n=xx+y*y)<=mx) {sv[n]=!sv[n]; y+=(d=6-d);}
  }
  r=Math.floor(z*0.5); // z*0.5 = sqrt(mx/4)
  for (x=1; x<=r; ++x) { // Boucle C
    xx=4*x*x; y=1; d=2;
    if (x%3) while ((n=xx+y*y)<=mx) {sv[n]=!sv[n]; y+=2;}
    else     while ((n=xx+y*y)<=mx) {sv[n]=!sv[n]; y+=(d=6-d);}
  }
  r=Math.floor(z);
  for (n=5; n<=r; ++n)
    if (sv[n]) for (nn=n*n,i=nn; i<=mx; i+=nn) sv[i]=false;
  return sv;
}
Et nous arrivons, à quelques détails près, au code (en Java) proposé dans Prime I.T. sous l'onglet Atkin, Troisième ou Quatrième implémentation, source.
 
 

Atkin4.js


Il semble qu'on ne puisse plus simplifier grand-chose. Pourtant, quelque chose me "démange" encore:
Les boucles intérieures (while) calculent n=xx+y*y à partir de y qui a été obtenue d'une manière "optimisée".
Question: ne pourrait-on pas directement obtenir n d'une manière "optimisée" ?
J'ai mis pas mal de temps pour faire ce travail assez "laborieux".

Adaptons notre "print" pour les valeurs de n (seconde partie de AtkinPrint_10000.txt).

Pour les trois boucles A,B,C, il "suffit" de trouver le code qui correspond à l'évolution des valeurs de n dans le "print".
function Atkin4(mx) {
  var a,b,d,e,n,r,x,z=Math.sqrt(mx);
  var sv=[false,false,true,true]; // for 0,1,2,3
  for (var i=4; i<=mx; ++i) sv[i]=false;
  r=Math.floor(z*0.7071067812);
  for (a=11,d=12,x=2; x<=r; ++x) { // Boucle A
    for (n=a,e=d,b=(x%3==0); (e>0)&&(n<=mx); e-=12,n+=(b=!b)?e:2*e) sv[n]=!sv[n];
    if (x%3==1) {a+=12; d+=12;} else a+=(x%3!=0)?d:2*d;
  }
  r=Math.floor(z*0.5773502692);
  for (x=1,d=0,a=7; x<=r; x+=2,a+=(d+=24)) { // Boucle B
    for (n=a  ,e=-12; n<=mx; n+=(e+=72)) sv[n]=!sv[n];
    for (n=a+12,e=12; n<=mx; n+=(e+=72)) sv[n]=!sv[n];
  }
  r=Math.floor(z*0.5);
  for (x=1,d=4,a=5; x<=r; ++x,a+=(d+=8)) { // Boucle C
    if (x%3) for (n=a,e=0; n<=mx; n+=(e+=8)) sv[n]=!sv[n];
    else {
      for (n=a  ,e=-24; n<=mx; n+=(e+=72)) sv[n]=!sv[n];
      for (n=a+24,e=24; n<=mx; n+=(e+=72)) sv[n]=!sv[n];
    }
  }
  r=Math.floor(z);
  for (n=5; n<=r; ++n)
    if (sv[n]) for (var nn=n*n,i=nn; i<=mx; i+=nn) sv[i]=false;
 return sv;
}
On constate que dans les boucles intérieures, les incréments de n ne sont pas constants, mais s'incrémentent eux-mêmes aussi, ce qui correspond à une sorte d'"incrémentation accélérée":
 
 

Atkin5.js


J'ai été très surpris de voir que dans Atkin4 la variable y ne figure plus nulle part !
Et la variable x ne sert plus qu'à parcourir les boucles et pour tenir compte de x%3.
On peut donc aussi "éliminer" x avec la limite a<=mx, et en "étalant" 3 fois l'intérieur des boucles qui utilisent x%3.
Pour la boucle A, cet intérieur est encore dédoublé pour éviter l'alternance introduite avec la variable booléenne b.
function Atkin5(mx) {
  var a,b,d,e,g,n;
  var sv=[false,false,true,true]; // for 0,1,2,3
  for (var i=4; i<=mx; ++i) sv[i]=false;
  for (a=11,d=12,g=24; a<=mx; a+=12,d+=12,g+=36) { // Boucle A
    for (n=a,  e=g+24; (e>=48)&&(n<=mx); n+=(e-=72)) sv[n]=!sv[n];
    a+=d;
    for (n=a-12,  e=g; (e>=48)&&(n<=mx); n+=(e-=72)) sv[n]=!sv[n];
    for (n=a,  e=g+36; (e>=48)&&(n<=mx); n+=(e-=72)) sv[n]=!sv[n];
    a+=2*d;
    for (n=a-24,e=g-12;(e>=48)&&(n<=mx); n+=(e-=72)) sv[n]=!sv[n];
    for (n=a,  e=g+24; (e>=48)&&(n<=mx); n+=(e-=72)) sv[n]=!sv[n];
    for (n=a+d-12,e=g; (e>=48)&&(n<=mx); n+=(e-=72)) sv[n]=!sv[n];
  }
  for (d=0,a=7; a<=mx; a+=(d+=24)) { // Boucle B
    for (n=a  ,e=-12; n<=mx; n+=(e+=72)) sv[n]=!sv[n];
    for (n=a+12,e=12; n<=mx; n+=(e+=72)) sv[n]=!sv[n];
  }
  for (d=4,a=5; a<=mx; a+=(d+=8)) { // Boucle C
    for (n=a,e=0; n<=mx; n+=(e+=8)) sv[n]=!sv[n];
    a+=(d+=8);
    for (n=a,e=0; n<=mx; n+=(e+=8)) sv[n]=!sv[n];
    a+=(d+=8);
    for (n=a  ,e=-24; n<=mx; n+=(e+=72)) sv[n]=!sv[n];
    for (n=a+24,e=24; n<=mx; n+=(e+=72)) sv[n]=!sv[n];
  }
  var r=Math.floor(Math.sqrt(mx));
  for (n=5; n<=r; ++n)
    if (sv[n]) for (var nn=n*n,i=nn; i<=mx; i+=nn) sv[i]=false;
  return sv;
}
Bizarre ..., ce code du crible d'Atkin qui ne comporte explicitement ni des testes sur n%12, ni des calcul de la forme n=kx²±y², ni même les variables x ou y !!!
L'algorithme est pourtant basé sur ces notions.
 
 

Mesures en ms


Veuillez patienter "une minute" lorsque vous lancez Atkin.html qui permet d'afficher vos tests mesures correspondant à:
Atkin0: mx=10, n=4, time=0 ms 
Atkin0: mx=100, n=25, time=0 ms 
Atkin0: mx=1000, n=168, time=0 ms 
Atkin0: mx=10000, n=1229, time=1 ms 
Atkin0: mx=100000, n=9592, time=4 ms 
Atkin0: mx=1000000, n=78498, time=44 ms 
Atkin0: mx=10000000, n=664579, time=399 ms 
Atkin0: mx=100000000, n=5761455, time=5265 ms 

Atkin1: mx=10, n=4, time=0 ms 
Atkin1: mx=100, n=25, time=0 ms 
Atkin1: mx=1000, n=168, time=0 ms 
Atkin1: mx=10000, n=1229, time=1 ms 
Atkin1: mx=100000, n=9592, time=4 ms 
Atkin1: mx=1000000, n=78498, time=42 ms 
Atkin1: mx=10000000, n=664579, time=478 ms 
Atkin1: mx=100000000, n=5761455, time=5232 ms 

Atkin2: mx=10, n=4, time=0 ms 
Atkin2: mx=100, n=25, time=0 ms 
Atkin2: mx=1000, n=168, time=1 ms 
Atkin2: mx=10000, n=1229, time=1 ms 
Atkin2: mx=100000, n=9592, time=4 ms 
Atkin2: mx=1000000, n=78498, time=42 ms 
Atkin2: mx=10000000, n=664579, time=373 ms 
Atkin2: mx=100000000, n=5761455, time=4029 ms 

Atkin3: mx=10, n=4, time=0 ms 
Atkin3: mx=100, n=25, time=0 ms 
Atkin3: mx=1000, n=168, time=0 ms 
Atkin3: mx=10000, n=1229, time=1 ms 
Atkin3: mx=100000, n=9592, time=2 ms 
Atkin3: mx=1000000, n=78498, time=31 ms 
Atkin3: mx=10000000, n=664579, time=297 ms 
Atkin3: mx=100000000, n=5761455, time=2905 ms 

Atkin4: mx=10, n=4, time=0 ms 
Atkin4: mx=100, n=25, time=0 ms 
Atkin4: mx=1000, n=168, time=0 ms 
Atkin4: mx=10000, n=1229, time=0 ms 
Atkin4: mx=100000, n=9592, time=1 ms 
Atkin4: mx=1000000, n=78498, time=19 ms 
Atkin4: mx=10000000, n=664579, time=270 ms 
Atkin4: mx=100000000, n=5761455, time=2799 ms 

Atkin5: mx=10, n=4, time=0 ms 
Atkin5: mx=100, n=25, time=0 ms 
Atkin5: mx=1000, n=168, time=0 ms 
Atkin5: mx=10000, n=1229, time=0 ms 
Atkin5: mx=100000, n=9592, time=4 ms 
Atkin5: mx=1000000, n=78498, time=20 ms 
Atkin5: mx=10000000, n=664579, time=270 ms 
Atkin5: mx=100000000, n=5761455, time=2786 ms
Le tableau ci-dessous n'a qu'une valeur comparative.
Les mesures dépendent de l'ordinateur, du navigateur et de leur charge.
Sur le même ordinateur, j'ai chaque fois effectué une série de tests et indiqué (en ms) le meilleur résultat.

Une liste actualisée d'articles sur les nombres premiers, complétée de mesures des temps d'exécution, peut être obtenue ici: Nombres premiers.
 
 
Testé avec:
Firefox            23.0     OK
Google Chrome      28.0     OK
Internet Explorer  11       OK
Opera              12.16    OK
Safari              5.1.7   OK

Si ça "bloque", n'allez pas jusqu'à mx=100000000 (dans Atkin.html: function Test() ).

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Commenter la réponse de William VOIROL

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.