Nombres premiers: Crible avec cycle additif

Télécharger le projet
Commenter

Description

Est-il vraiment nécessaire de prévoir une place en mémoire pour les éléments du crible d'Eratosthène qui correspondent aux nombres pairs > 2, alors qu'on sait qu'il faudra tous les neutraliser ?
Et on peut se poser la même question pour les multiples de 3, 5, 7, 11, ... .

Cet article est une première partie de la méthode des cycles additifs qui permet de "systématiser" cette idée.
Et dont un des buts est de répondre à la question:
Jusqu'à quel nombre premier est-il avantageux d'aller pour en éliminer à l'avance les multiples ?
 
 

Nombres premiers: Crible avec cycle additif


Pour tester les codes Cycle_A, Cycle_B, Cycle_C, Cycle23, Cycle235, Cycle2357 et en mesurer l'efficacité, exécutez le fichier Cycle.html.

Si d'autres méthodes sur les nombres premiers vous intéressent: ==> Résumé de mes articles sur les nombres premiers.
 
 

Cycle_A


Nous partons directement de SIEVE2.JS (voir crible d'Eratosthène): 
function Sieve(mx) { // Sieve2.js: mx>=3
  var h=1+Math.floor((mx-3)/2),i,j,p,sv=[]; // sv=new Array(h)
  for (i=0; i<h; i++) sv[i]=true;
  for (i=0,p=3; p*p<=mx; i++,p+=2)
    if (sv[i]) // p is prime
      for (j=i+p; j<h; j+=p) sv[j]=false;
  return sv; // 2 is not included
}
où, sachant que le premier nombre premier est 2, on peut se limiter à ne traiter que les nombres non multiples de 2, c'est-à-dire les nombres impairs > 2.

Considérons maintenant les deux nombres premiers 2 et 3, et représentons le "masque" des entiers non divisibles par l'un ou l'autre.
Comme les valeurs q augmentent alternativement de 2 et 4, on parle d'un cycle additif défini par cyc=[2,4]. 
//  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 ...
// ##    ##          ##    ##          ##    ##          ##    ##
//
// Vecteur (array) des candidats q (d'index i) restants:
// i   0  1, 2  3, 4  5, 6  7, 8  9,10 11,12 13,14 15,16 17,18 19,20 ...
// q   5  7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 ...
//
  cyc=[2,4];
  r=Math.floor(Math.sqrt(mx));
  
// La boucle suivante permet de parcourir simultanément i et q:
  q=5;
  for (i=0; q<=r; i++) {
    ...
    q+=cyc[i%2]; // ajoute alternativement 2 et 4
  }
  
// Ou de manière plus condensée:
  for (i=0,q=5; q<=r; q+=cyc[(i++)%2]) { ... }


Le nombre de candidats<=mx qui restent est un peu difficile à calculer:
h = ((mx-5-a)/3+((a>1)? 2: 1)) , où a = (mx-5)%6.

En parcourant les candidats q (d'index i), lorsqu'on tombe sur un nombre premier (sv[i] true), on élimine tous ses multiples p (d'index j). 
function Cycle_A(mx) { // mx >= 5
  var cyc=[2,4]; // cycle avec 2,3 comme nombres premiers connus
  var a=(mx-5)%6,h=((mx-5-a)/3+((a>1)?2:1)),i,j,p,q,r=Math.floor(Math.sqrt(mx)),sv=[];
  for (i=0; i<h; i++) sv[i]=true;
  for (i=0,q=5; q<=r; q+=cyc[(i++)%2])
    if (sv[i]) { // q is prime
      for (j=i+1,p=q+cyc[i%2]; j<h; p+=cyc[(j++)%2])
        if (p%q==0) sv[j]=false;
    }
  return sv; // 2,3 not included
}

Le temps d'exécution de ce code est assez mauvais, car en fait, on y utilise le test par division pour éliminer les candidats.
 
 

Cycle_B


Le tableau suivant montre que le masque des candidats q multiples de p premier est cyclique sur 6p (les indexes sur 2p).
Nous allons donc déterminer les multiples de p dans le segment [p+cyc[i%2] .. p+6p] ([i+1 .. i+2p] pour les indexes), et traiter les séries espacées de 6p (2p pour les indexes):
Constatons aussi que chaque segment compte 2 multiples de p 
// i     0  1, 2  3, 4  5, 6  7, 8  9,10 11,12 13,14 15,16 17,18 19,20 21,22 23,24 25,26 27,28 29 ...
// q     5  7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 ...
// p=5  ##                   ##       ##                   ##       ##                   ##
// p=7     ##                         ##             ##                         ##             ##
// p=11       ##                                           ##                   ##
// p=13          ##                                                 ##                         ##
//
function Cycle_B(mx) { // mx >= 5
  var cyc=[2,4]; // cycle avec 2,3 comme nombres premiers connus
  var a=(mx-5)%6,h=((mx-5-a)/3+((a>1)?2:1)),i,j,p,q,r=Math.floor(Math.sqrt(mx)),sv=[];
  for (i=0; i<h; i++) sv[i]=true;
  for (i=0,p=5; p<=r; p+=cyc[(i++)%2])
    if (sv[i]) { // p is prime
      var c,p2=2*p,p6=6*p;
      for (q=cyc[i%2],c=i+1; q<=p6; q+=cyc[(c++)%2])
        if (q%p==0) // q est divisible par p
          for (j=c; j<h; j+=p2) sv[j]=false;
    }
  return sv; // 2,3 not included
}

Le fichier [] (ou le tableau de mesures ci-dessous) montre que Cycle_B est plus rapide que Sieve3 !
 
 

Cycle_C


Nous voyons qu'il suffit, avec un nombre premier p, d'agir sur les candidats à partir de p*p (d'index (p*p-4)/3): 
function Cycle_C(mx) { // mx >= 5
  var cyc=[2,4]; // cycle avec 2,3 comme nombres premiers connus
  var a=(mx-5)%6,h=((mx-5-a)/3+((a>1)?2:1)),i,j,p,q,r=Math.floor(Math.sqrt(mx)),sv=[];
  for (i=0; i<h; i++) sv[i]=true;
  for (i=0,p=5; p<=r; p+=cyc[(i++)%2])
    if (sv[i]) { // p is prime
      var ii=p*p,dj=2*p,c=(ii-4)/3; // avance jusqu'à p*p
      for (j=c; j<h; j+=dj) sv[j]=false;
      q=ii; do {q+=cyc[(c++)%2]} while (q%p); // avance jusqu'au second multiple
      for (j=c; j<h; j+=dj) sv[j]=false;
    }
  return sv; // 2,3 not included
}

L'amélioration est minime.
 
 

Cycle23


La manière de chercher des multiples dans un segment de longueur 6p peut être améliorée.
Analysons l'intervalle p < q <= p+6p d'indexes i = j <= i+2p:
Il comporte 2p nombres commençant par p+cyc[i%2] et dont les incréments successifs sont: cyc[(i+1)%2], cyc[(i+2)%2], ... cyc:[(i+2p)%2].

Voici la liste des incréments par rapport à p, si i est pair: 2, 6, 8, 12, ... 2p-4, 2p, et si i est impair: 4, 6, 10, 12, ... 2p-2, 2p.
Dans les deux cas on peut partager la liste en deux listes de p éléments dont les incréments successifs sont 6 (donc 2 pour les indexes).
La première, si i pair: 2, 8, ... 2p-4, si i est impair: 4, 12, ... 2p-2; et la seconde: 6, 12, ... 2p .

On peut montrer que chacune des listes de p éléments ne comporte qu'un seul nombre multiple de p. Une fois ce nombre q (d'index c) trouvé, il suffit d'éliminer les nombres de valeur q, q+6p, q+12p, q+18p, ... d'indexes c, c+2p, c+4p, c+6p, ... : 
// i     0  1, 2  3, 4  5, 6  7, 8  9,10 11,12 13,14 15,16 17,18 19,20 21,22 23,24 25,26 27,28 29 ...
// q     5  7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 ...
// p=5  ##                   ##       ##                   ##       ##                   ##
// p=7     ##                         ##             ##                         ##             ##
// p=11       ##                                           ##                   ##
// p=13          ##                                                 ##                         ##
//
function Cycle23(mx) { // mx >= 5
  var pri=5,cyc=[2,4],len=2,gap=6; // cycle avec 2,3 comme nombres premiers connus
  var a=(mx-pri)%gap,h=((mx-pri-a)/3+((a>1)?2:1)),i,j,p,ps; // ps: p suivant
  var r=Math.floor(Math.sqrt(mx)),sv=[];
  for (i=0; i<h; i++) sv[i]=true;
  for (i=0,p=pri,ps=p+2; p<=r; p=ps,ps+=cyc[(++i)%len])
    if (sv[i]) { // p is prime
      var pl=p*len;
      for (j=(p*p-4)/3; j<h; j+=pl) sv[j]=false;
      for (j=(p*ps-5)/3; j<h; j+=pl) sv[j]=false;
    }
  return sv; // 2,3 not included
}

Comme espéré, le temps de calcul diminue.
 
 

Cycle235


Nous allons maintenant éliminer d'avance tous les multiples de 2,3 et 5, en utilisant, à partir du nombre premier pri=7, le cycle additif cyc=[4,2,4,2,4,6,2,6] avec len=8 et gap=30.
Rappelons que:
a) Le masque des candidats q multiples de p premier est cyclique sur des segments de gap*p éléments (len*p indexes).
b) Chaque segment contient len multiples de p (dans Cycle23, 
// i     0  1  2  3  4  5  6  7, 8  9 10 11 12 13 14 15,16 17 18 19 20 21 22 23,24  25  26  27  28  29  30  31, 32  33  34  35  36  37  38  39, 40  41  42  43  44  45  46  47, 48  49  50  51  52  53  54  55, 56 ...
// q     7 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 83 89 91 97 101 103 107 109 113 119 121 127 131 133 137 139 143 149 151 157 161 163 167 169 173 179 181 187 191 193 197 199 203 209 211 217 ...
// p=7  ##                                  ##                   ##          ##                         ##              ##                          ##                                              ##
// p=11    ##                                                                                               ##                      ##                                          ##                      ##
// p=13       ##                                                                                                                                                ##
//
function Cycle235(mx) { // mx>=7
  var pri=7,len=8,gap=30,cyc=[4,2,4,2,4,6,2,6]; // cycle with prims 2,3,5
  var e,h=len*Math.floor((mx-pri)/gap),j,p,p2,mm=Math.floor(Math.sqrt(mx)),q,sv=[];
  for (j=0,p=pri+gap*(h/len); p<=mx; p+=cyc[j++]) h++; // sv=new Array(h)
  for (i=0; i<h; i++) sv[i]=true;
  for (i=0,p=pri; p<=mm; p+=cyc[(i++)%len])
    if (sv[i]) { // p is prime
      var p2=p*2,pl=p*len,pp=p*p;
      for (k=0,q=pri; k<len; q+=cyc[k],k++) // pour chaque élément du cycle
        for (j=pp; j<=mx; j+=p2) // on cherche un multiple depuis p*p
          if ((j-q)%gap==0) {
            for (e=k+len*((j-q)/gap); e<h; e+=pl) sv[e]=false;
            break;
          }
    }
  return sv; // 2,3,5 not included
}

 
 

Cycle2357


Par acquis de conscience, testons encore explicitement le cycle additif "généré" par les nombres premiers 2,3,5,7: 
function Cycle2357(mx) { // mx>=11
  var pri=11,len=48,gap=210,cyc=[2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4
    ,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10]; // cycle with prims 2,3,5,7
  var e,h=len*Math.floor((mx-pri)/gap),j,p,p2,mm=Math.floor(Math.sqrt(mx)),q,sv=[];
  for (j=0,p=pri+gap*(h/len); p<=mx; p+=cyc[j++]) h++; // sv=new Array(h)
  for (i=0; i<h; i++) sv[i]=true;
  for (i=0,p=pri; p<=mm; p+=cyc[(i++)%len])
    if (sv[i]) { // p is prime
      var p2=p*2,pl=p*len,pp=p*p;
      for (k=0,q=pri; k<len; q+=cyc[k],k++)
        for (j=pp; j<=mx; j+=p2)
          if ((j-q)%gap==0) {
            for (e=k+len*((j-q)/gap); e<h; e+=pl) sv[e]=false;
            break;
          }
    }
  return sv; // 2,3,5,7 not included
}

 
 

Conclusion (provisoire)


On peut constater que les fonctions Cycle235 et Cycle2357 ne diffèrent que par l'initialisation des variables pri, len, gap et cyc, qui définissent le cycle utilisé.
La suite de mes articles sers basé sur l'objet Cycle qui, je l'espère, permettra d'un peu mieux cerner l'importance du niveau (ou taille) du cycle dans le compromis mémoire utilisée - temps de calcul.

Voici un autre éclairage sur le sujet: algorithme additif et itératif.
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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.

Du même auteur (William VOIROL)