Un Crible d'Atkin bizarre
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++.
Nous partons du code suivant correspondant à Atkin2.js:
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.
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".
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.
L'algorithme est pourtant basé sur ces notions.
Veuillez patienter "une minute" lorsque vous lancez Atkin.html qui permet d'afficher vos tests mesures correspondant à:
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:
Si ça "bloque", n'allez pas jusqu'à mx=100000000 (dans Atkin.html: function Test() ).
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 msLe 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
- Un Crible d'Atkin bizarre
- Crible d'eratosthene - Forum C
- Crible quadratique - Forum Visual Basic
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.