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.
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.