Nombres premiers: Crible d'Atkin

Soyez le premier à donner votre avis sur cette source.

Vue 2 965 fois - Téléchargée 473 fois

Description

Pour la définition, voir Nombres premiers.
Une version actualisée de l'introduction, complétée de mesures des temps d'exécution, peut être obtenue ICI.
 
 

Nombres premiers: Crible d'Atkin


Voir: Crible d'Atkin

Avantage de l'algorithme: temps d'exécution rapide.
Désavantage: programmation plus compliquée, utilise un tableau (bool) de tous les nombres candidats.
 
 

Atkin0.js


Pour commencer, voici un code 'classique' qui correspond au pseudo-code donné par WickyPedia sous le titre "Sieve of Atkin":
function Atkin(mx) { // Atkin0.js
  var i,n,x,y,yy,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++) {
    var xx=x*x;
    for (y=1; y<=r; y++) {
      yy=y*y;
      n=3*xx-yy;
      if (x>y && n<=mx && (n%12==11)) sv[n]=!sv[n];
      n=3*xx+yy;
      if (n<=mx && (n%12==7)) sv[n]=!sv[n];
      n=4*xx+yy;
      if (n<=mx && (n%12==1||n%12==5)) sv[n]=!sv[n];
    }
  }
  for (n=5; n<=r; n++)
    if (sv[n]) for (x=n*n,i=x; i<=mx; i+=x) sv[i]=false;
  for (i=0,n=0; i<=mx; i++) if (sv[i]) n++; // i is prime
  return n;
}

Test direct
 
 

Atkin1.js


Optimisons le calcul des valeurs utilisées dans les boucles:
function Atkin(mx) { // Atkin1.js
  var d,i,n,x,y,xx,xx3,yy,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,xx=1,xx3=3; xx<=mx; x++,xx=x*x,xx3=3*xx)
    for (y=1,yy=1; yy<=mx; y++,yy=y*y) {
      n=xx3-yy; if (x>y && n<=mx && (n%12==11)) sv[n]=!sv[n];
      n+=yy+yy; if (n<=mx && (n%12==7)) sv[n]=!sv[n];
      n+=xx;    if (n<=mx && (n%12==1||n%12==5)) sv[n]=!sv[n];
    }
  for (n=5; n<=r; n++)
    if (sv[n]) for (x=n*n,i=x; i<=mx; i+=x) sv[i]=false;
  for (i=0,n=0; i<=mx; i++) if (sv[i]) n++; // i is prime
  return n;
}

Test direct
 
 

Atkin2.js


Faisons 3 boucles internes adaptées aux limites particulières:
function Atkin(mx) { // Atkin2.js
  var d,i,n,x,y,xx,yy,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++) {
    xx=3*x*x;
    for (y=1; y<x; y++) if ((n=xx-y*y)<=mx && (n%12==11)) sv[n]=!sv[n];
    if (xx<mx)
      for (y=1; y<=r; y++) if ((n=xx+y*y)<=mx && (n%12==7)) sv[n]=!sv[n];
    xx+=x*x;
    if (xx<mx)
      for (y=1; y<=r; y++) if ((n=xx+y*y)<=mx && (n%12==1||n%12==5)) sv[n]=!sv[n];
  }
  for (n=5; n<=r; n++)
    if (sv[n]) for (x=n*n,i=x; i<=mx; i+=x) sv[i]=false;
  for (i=0,n=0; i<=mx; i++) if (sv[i]) n++; // i is prime
  return n;
}

Test direct
J'avoue que je suis un peu déçu de mes résultats obtenus.
Pourrait-on obtenir une amélioration significative en ne traitant que les impairs ? L'adaptation ne semble pas très simple.
Ou quelqu'un connaitrait-il une meilleure version de cet algorithme ?
 
 

Mesures


Le tableau ci-dessous, qui n'a qu'une valeur comparative, montre que les "meilleurs" codes basés sur l'algorithme "crible d'Askin" sont pratiquement limités aux nombres premiers inférieurs à 100 millions.
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é le meilleur résultat.

Temps d'execution en ms:
 Max:  1000  10000  100000  1000000  10000000  100000000   
 n:  168  1229  9592  78498  664579  5761455  memory: 
 Div0  2  63  3365  -  -  -  0 
 Div1  1  42  1770  145128  -  -  0 
 Div2  0  2  35  309  7579  -  0 
 Div3  0  2  31  305  6799  -  0 
 Div4  0  1  30  296  6564  -  0 
 List0  0  1  26  323  7301  -  int[n] 
 List1  0  1  19  172  2557  -  int[n] 
 Sieve0  0  1  11  79  659  7104  bool[Max] 
 Sieve1  0  1  9  63  466  5003  bool[Max] 
 Sieve2  0  1  2  20  142  1495  bool[Max/2] 
 Sieve3  0  0  1  23  138  1455  bool[Max/2] 
 Atkin0  0  0  3  29  407  4801  bool[Max] 
 Atkin1  0  0  3  30  384  4777  bool[Max] 
 Atkin2  0  0  5  37  360  4154  bool[Max] 

Accédez aux tests et sources de tous mes travaux sur les nombres premiers ICI (sous Maths, Nombres premiers)
 
 
Testé avec:
 Firefox  22.0  OK 
 Google Chrome  28.0  OK 
 Internet Explorer  10.0.7  OK 
 Opera  22.0   OK 
 Safari   22.0  OK 

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
313
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
26 mai 2020
2
Bonjour William VOIROL,
C'est très intéressant de publier plusieurs solutions pour le même problème.

Ici on calcule en Javascript un indicateur pour chaque nombre entre 1 et nmax (exemple : nmax = 100 000 000) selon qu'il est premier ou non. Ceci est un problème différent du calcul du nombre premier immédiatement inférieur (ou supérieur) à un nombre donné. Et c'est aussi, bien sûr, différent du calcul pour savoir si un nombre donné est premier ou non. J'ai traité en C++ le même problème que celui traité ici.
A : http://codes-sources.commentcamarche.net/source/53321-crible-d-eratosthene-optimise on peut voir qu'il est assez facile de marquer les 203268793 nombres premiers entre 1 et 4294709602 (4 294 709 602).

De plus, avec la variante qui y est référencée et qui utilise les entiers int64 en mode x64 on peut aller beaucoup plus loin et, par exemple, marquer les 4 118 054 813 nombres entiers entre 1 et 100 000 000 000 en quelques dizaines de minutes.

D'où mes questions : 1°) est-ce que Javascript peut calculer aussi bien et aussi vite que C++ avec de grands entiers ou bien a-t-il une limitation plus contraignante que C++ ? Et si oui laquelle ? 2°) Est-ce que le crible d'Atkin est plus rapide que la crible d'Ératosthène ?

Merci, pgl10
Messages postés
707
Date d'inscription
mercredi 17 novembre 2004
Statut
Membre
Dernière intervention
29 septembre 2013
>
Messages postés
313
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
26 mai 2020

Sans vouloir m'avancer dans un traitement comme celui ci le C++ restera quoi qu'il en soit plus rapide en terme de traitement (notamment parce qu'il peut etre multi-threadé, et que la gestion des allocations mémoire est réalisable tout a la main). Néanmoins en C++ tout dépendra de comment cela a été codé (optimisation, compilation pour un type précis de proco...). Mais pour un avis détaillé il faudrai voir dans la rubrique C/C++ du forum.

Quoi qu'il en soit source sympa, un bon truc de matheux presque incompréhensible quand on maitrise pas le sujet xD mais néanmoins chapeau pour le portage en js (meme si je ne comprend toujours pas l'interet de l'usage du cryble d'Atkin dans la vie de tous les jours)

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.