Nombres premiers: Crible avec cycle additif Bis

Soyez le premier à donner votre avis sur cette source.

Vue 1 815 fois - Téléchargée 162 fois

Description

Voici la première suite de l'article Crible avec cycle additif.
où on utilise explicitement les cycles additifs {2}, {2,4}, {4,2,4,2,4,6,2,6},
{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},
basés respectivement sur les nombres premiers déjà connus [2], [2,3], [2,3,5], [2,3,5,7], pour "éliminer" (dans un crible d'Eratosthène) de façon anticipée les candidats multiples de ces nombres premiers.

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

Avec CycleOut (ou avec CycleOut.html du zip), vous pouvez obtenir (par exemple) les 664579 nombres premiers <= 10000000 en une ou deux secondes (calcul et affichage) !
 
 

Nombres premiers: Crible avec cycle additif Bis


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é.
Précisons ces valeurs et montrons comment elles évoluent:
prms connus      pri   len    gap  gap/len  cyc                          candidats restants
-                  2     1      1  1        {1}                          2,3,4,5,6,7,8,...
2                  3     1      2  2        {2}                          3,5,7,9,11,13,15,17,...
2,3                5     2      6  3        {2,4}                        5,7,11,13,17,19,23,25,29,...
2,3,5              7     8     30  3.75     {4,2,4,2,4,6,2,6}            7,11,13,17,19,23,29,31,37,41,...
2,3,5,7           11    48    210  4.375    {2,4,2,4,6,2,6,4,2,4,6,...}  11,13,17,19,23,29,31,37,41,43,47,...
2,3,5,7,11        13   480   2310  4.8125   {4,2,4,6,2,6,4,2,4,6,6,...}  13,17,19,23,29,31,37,41,43,47,53,...
2,3,5,7,11,13     17  5760  30030  5.21354  {2,4,6,2,6,4,2,4,6,6,2,...}  17,19,23,29,31,37,41,43,47,53,...
2,3,5,7,11,13,17  19 92160 510510  5.53939  {4,6,2,6,4,2,4,6,6,2,6,...}  19,23,29,31,37,41,43,47,53,...
...

pri est le nombre premier à partir duquel on applique le cycle additif pour trouver les candidats suivants.
gap désigne la somme des éléments du cycle, et qui correspond au produit des nombres premiers < pri: 2=2, 6=2*3, 30=2*3*5, 210=2*3*5*7, ...
len est le nombre l'éléments du cycle qui est obtenu en multipliant les nombres premiers diminués de 1: 1=(2-1), 2=(2-1)*(3-1), 8=(2-1)*(3-1)*(5-1), 48=(2-1)*(3-1)*(5-1)*(7-1), ...
gap/len est le facteur de réduction de la mémoire utilisée pour le crible.

Une manière de calculer un "cycle" particulier serait d'utiliser un crible pour les entiers entre (pri+1) et (pri+gap), d'y annuler les multiples des nombres premiers plus petit que pri, puis de relever la différences des indexes consécutifs des éléments restants.
Mais nous allons construire l'objet Cycle muni d'une fonction Next() qui, à partir d'un cycle donné, permet de calculer "récursivement" le cycle "suivant".
 
 

L'objet Cycle


Créons l'objet Cycle et la fonction Next():
function Cycle() {this.pri=2; this.len=1; this.gap=1; this.cyc=[1];}

Cycle.prototype.Next=function() {
  var cyc=[],e=this.cyc[0],r=e,i=0,j=0,p=this.pri,len=this.len*(p-1);
  do {
    if (++i>=this.len) i=0; // plus rapide que d'utiliser [i%this.len]
    if ((r+=this.cyc[i])%p) {cyc[j++]=r-e; e=r;}
  } while (j<len);
  this.pri+=this.cyc[0]; this.len=len; this.gap*=p; this.cyc=cyc;
}

Le programme Cycles.html,qui donne les résultats suivant, vous permet de tester cet objet:
Calcul des cycles:
pri=2, len=1, gap=1;  gap/len=1;  temps de calcul: 0 ms
  cyc=[1]
pri=3, len=1, gap=2;  gap/len=2;  temps de calcul: 0 ms
  cyc=[2]
pri=5, len=2, gap=6;  gap/len=3;  temps de calcul: 0 ms
  cyc=[2,4]
pri=7, len=8, gap=30;  gap/len=3.75;  temps de calcul: 0 ms
  cyc=[4,2,4,2,4,6,2,6]
pri=11, len=48, gap=210;  gap/len=4.375;  temps de calcul: 0 ms
  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]
pri=13, len=480, gap=2310;  gap/len=4.8125;  temps de calcul: 0 ms
  cyc=[4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,4,6,2,10,2,6,6,4,2,4,6,2,10,2,4,2,12,10,2,4,2,4,6,2,6,...]
pri=17, len=5760, gap=30030;  gap/len=5.213541666666667;  temps de calcul: 0 ms
  cyc=[2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,4,6,2,10,2,6,6,4,6,6,2,10,2,4,2,12,12,4,2,4,6,2,10,6,6,6,...]
pri=19, len=92160, gap=510510;  gap/len=5.539388020833333;  temps de calcul: 5 ms
  cyc=[4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,4,6,2,10,2,6,6,4,6,6,2,10,2,4,2,12,12,4,2,4,6,2,10,6,6,6,2,...]
pri=23, len=1658880, gap=9699690;  gap/len=5.847131799768518;  temps de calcul: 91 ms
  cyc=[6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,4,6,2,10,2,6,6,4,6,6,2,10,2,4,2,12,12,4,2,4,6,2,10,6,6,6,2,6,...]
pri=29, len=36495360, gap=223092870;  gap/len=6.112910517939815;  temps de calcul: 836 ms
  cyc=[2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,4,6,2,10,2,6,6,4,6,6,2,10,2,4,2,12,12,4,2,4,6,2,10,6,6,6,2,6,4,...]
  
Élément max: 40

L'élément max n'est calculé que pour le dernier cycle.

Voici un autre algorithme assez semblable: algorithme additif et itératif.
 
 

Cycle_Test.html


Nous voici prêt pour réaliser un code "général", basé sur Cycle235 et Cycle2357, qui permet l'utilisation d'un cycle de niveau quelconque.
Limitons-nous tout de même au moins au domaine des entiers 32 bits: gap < 2³², donc 2 <= pri <= 29.
Cycle.prototype.Sieve=function(mx) {
  var e,h=this.len*Math.floor((mx-this.pri)/this.gap);
  var j,p,p2,mm=Math.floor(Math.sqrt(mx)),q,sv=[];
  for (j=0,p=this.pri+this.gap*(h/this.len); p<=mx; p+=this.cyc[j++]) h++; // sv=new Array(h)
  for (i=0; i<h; i++) sv[i]=true;
  for (i=0,p=this.pri; p<=mm; p+=this.cyc[(i++)%this.len])
    if (sv[i]) { // if p is prime
      var p2=p*2,pl=p*this.len,pp=p*p;
      for (k=0,q=this.pri; k<this.len; q+=this.cyc[k],k++)
        for (j=pp; j<=mx; j+=p2)
          if ((j-q)%this.gap==0) {
            for (e=k+this.len*((j-q)/this.gap); e<h; e+=pl) sv[e]=false;
            break;
          }
    }
  return sv; // primes < pri not included
}

La capture jaune de l'article montre les résultats du code Cycle_Test.html.

Quelle déception !!!
 
 

Conclusion (provisoire)


Les résultats ne s'améliorent que jusqu'à pri=11, puis, ils s'empirent très rapidement.

En ce qui concerne le temps de calcul, il semble donc illusoire d'aller plus loin que le cycle basé sur [2,3,5,7]: pri=11, len=48, gap=210; gap/len=4.375; 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].

Ou serait-il possible d'améliorer le passage de Cycle23 à Cycle235, Cycle2357 ou Cycle.Sieve ?

Le gain en place mémoire gap/len pour le crible sv s'améliore de moins en moins, surtout qu'il faut ajouter la taille du cycle lui-même, qui augmente rapidement.

Pour la troisième suite de cet article, je vais essayer de tenir compte de ces remarques.

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.