Nombres premiers: crible d'Eratosthène
William VOIROL
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019
-
30 sept. 2013 à 08:35
pgl10 Messages postés 381 Date d'inscription samedi 18 décembre 2004 Statut Non membre Dernière intervention 25 avril 2024 - 31 oct. 2013 à 11:48
pgl10 Messages postés 381 Date d'inscription samedi 18 décembre 2004 Statut Non membre Dernière intervention 25 avril 2024 - 31 oct. 2013 à 11:48
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/100145-nombres-premiers-crible-d-eratosthene
https://codes-sources.commentcamarche.net/source/100145-nombres-premiers-crible-d-eratosthene
31 oct. 2013 à 11:48
Pour répondre à :
Question: serait-il possible de la diminuer encore en éliminant d'avance également les multiples de 3 ? Et pourquoi pas aussi les multiples de 5, 7, 11, ... ?
j'ai programmé un crible d'Eratosthène dans lequel on évite les multiples de 2, 3, 5 et 7 dans le crible. On observe 1°) une réduction sensible de la taille du crible 2°) une petite réduction du temps de calcul du crible 3°) mais aussi une augmentation du temps de parcours du crible dans la phase suivante où on compte les nombres premiers. En effet dans cette seconde phase il faut vérifier si chaque nombre candidat est un multiple de 2, 3, 5 ou 7 avant d'utiliser le crible, ce qui ralentit considérablement cette étape. En résumé cette méthode est intéressante quand on veut absolument diminuer la mémoire utilisée ou quand on veut utiliser le crible pour quelques nombres et pas pour tous.
17 oct. 2013 à 11:57
En épurant d'avance le crible des nombres pairs, on a pu diviser la mémoire utilisée en deux. Question: serait-il possible de la diminuer encore en éliminant d'avance également les multiples de 3 ? Et pourquoi pas aussi les multiples de 5, 7, 11, ... ?
Cette "généralisation" correspond à l'article "Nombres premiers: Crible avec cycle additif" que j'essaye de terminer prochainement.
Le fait d'avoir écrit xyz>>5 à la place de xyz/32 semble avoir dissimulé une qualité essentielle du code SieveC: l'optimisation maximale de la mémoire en n'utilisant qu'un seul "bit" par élément du crible (déjà restreint aux nombres impairs).
En effet, pour mx=1'000'000'000 par exemple, on alloue 500'000'000 "bits" ou 62'500'000 "bytes (char)" ou 15'625'000 "u32". SieveC passe donc de 500 Mo à 62.5 Mo (division par 8 par rapport à SieveB, comme mentionné) tout en améliorant le temps d'exécution !!!
Pour simuler un grand tableau de "bits" (valeurs vrai-faux ou 0-1), il est souvent conseillé de se baser sur les 8 bits d'un char (ou unsigned char). Après quelques mesures, j'ai constaté une amélioration de quelques % en me basant plutôt les 32 bits d'un unsigned _int32 (u32).
Pour essayer de "situer" le code SieveC par rapport à d'autres qui permettent également de déterminer le crible d'Eratosthène avec une valeur maximale mx <= 4'294'709'602 (correspond à 203'268'793 nombres premiers), je donne ici quelques mesures (même ordinateur et compilateur):
année, temps d'exec., mémoire, lien:
2003, 53.461 s, bit[Max/2], 1 000 000 de nombres premiers en 0.062 secondes
2011, 63.773 s, bit[Max/2], Crible d'eratosthène optimisé
2013, 23.167 s, bit[Max/2], SieveC
Aidez-moi à améliorer, compléter ou corriger cette liste.
Voir également: Nombres premiers.
2 oct. 2013 à 16:26
Dans un premier temps on marque les multiples impairs de 3 séparément.
De toutes façons, il faut bien les marquer dans cette méthode. Mais ensuite
non seulement il n'est plus nécessaire nécessaire de les examiner => p+=s
avec s : 2 ou 4 mais en plus il n'est plus nécessaire de marquer le multiples
de p qui sont aussi multiples de 3 => j+=t*p; avec t : 1 ou 2 Ce qui donne :
u32* Sieve(u32 mx) { // Utilisation bitset u32 i, j, p, pp, s, t, h=(mx-1)/2, n=(h+31)>>5; // nombres impairs u32* sv=(u32*)malloc(n*sizeof(u32)); for (i=0; i<n; i++) sv[i]=0XFFFFFFFF; // All true for (j=3; j<h; j+=3) sv[j>>5]&=(~(1<<(j&31))); // les multiples impairs de 3 s=4; for (p=5, pp=25; pp<=mx; p+=s, pp=p*p) { // les multiples de 3 sont évités i=(p-3)/2; s=6-s; if (sv[i>>5]&(1<<(i&31))) { // p is prime if(((i+2)*i)%3) t=1; else t=2; for (j=(pp-3)/2; j<h; j+=t*p) { // les multiples de 3 sont déjà marqués t=3-t; sv[j>>5]&=(~(1<<(j&31))); // SetFalse } } } return sv; // 2 non inclus }Chez moi cela gagne plus de 20% du temps d'exécution.30 sept. 2013 à 21:52
La comparaison de plusieurs méthodes pour résoudre le même problème est un avantage très intéressant.
A titre d'amusement on peut programmer ici la variante suivante dans SieveC :
1°) déclarer au début de u32* Sieve(u32 mx) { ... } :
u32 z[32] = {
0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFB, 0xFFFFFFF7, 0xFFFFFFEF, 0xFFFFFFDF, 0xFFFFFFBF, 0xFFFFFF7F,
0xFFFFFEFF, 0xFFFFFDFF, 0xFFFFFBFF, 0xFFFFF7FF, 0xFFFFEFFF, 0xFFFFDFFF, 0xFFFFBFFF, 0xFFFF7FFF,
0xFFFEFFFF, 0xFFFDFFFF, 0xFFFBFFFF, 0xFFF7FFFF, 0xFFEFFFFF, 0xFFDFFFFF, 0xFFBFFFFF, 0xFF7FFFFF,
0xFEFFFFFF, 0xFDFFFFFF, 0xFBFFFFFF, 0xF7FFFFFF, 0xEFFFFFFF, 0xDFFFFFFF, 0xBFFFFFFF, 0x7FFFFFFF};
2°) alors on peut, si on le veut, remplacer : sv[j>>5]&=(~(1<<(j&31)));
par : sv[j>>5]&=z[j&31]; ( ou même : sv[j>>5]&=z[j%32]; )
Cela effectue la même action, cela fait un calcul plus simple mais au prix d'un chargement mémoire en plus.
Chez moi cela gagne quelques petits pourcentages en temps d'exécution. Ce n'est donc pas significatif.
A chacun son choix !
30 sept. 2013 à 20:41
"J'y remplace simplement le type char par bool"
Quel intérêt ? char et bool font tous les deux 1 octet...
"Essayons d'utiliser la notion de "pointeur", dans le but de remplacer dans la boucle intérieure sv[j]=false par *s=false"
Là encore, pourquoi ? sv[j] c'est la même chose que *s+j, donc une fois compilé ces deux syntaxes différentes sont en fait strictement équivalentes en assembleur.
"L'amélioration n'est pas flagrante"
Bah non, c'est normal...
"à l'air d'être performant, surtout utilisé "inline""
Les appels aux fonctions sont coûteux, ça fait des allers-retours dans la mémoire, ça copie les valeurs dans les paramètre, ça copie le résultat...
Là encore c'est normal que ce soit meilleur "inline".
Je pense qu'il vaux mieux te concentrer sur les améliorations algorithmiques que structurelles des langages, ou alors passes directement à l'assembleur...
Tu parlais de la crible d'Atkin c'est une vraie idée d'amélioration.
Mais l'intérêt de lister les petits nombres premiers (les premiers milliards on les connaît déjà) est assez limité. Il est plus intéressant (surtout en cryptographie) de s'intéresser aux nombres premiers très grands (ordre de grandeur 10^100 ~ 10^1000).
Modifié par KX le 30/09/2013 à 19:48
Avec la manipulation bit à bit, on peux mettre 8 booléens dans un char, on divise donc la mémoire par 8, pour une augmentation du temps qui devrait être assez insignifiante (il faudrait faire des tests, mais je pense pas que ça dépasse 20%)
Quand on sait qu'on est ici en train de faire des calculs sur 1 000 000 000 de valeurs en 4 secondes, je pense qu'il est prioritaire d'économiser la mémoire (passer de 950 Mo à 120 Mo) quitte à diminuer la vitesse (passer de 4 à 5 secondes...)
À méditer ;-)
30 sept. 2013 à 11:49
Ce serait une cata en terme de perfs si c'était le cas.
Je rappelle qu'un BIT n'est pas adressable, il est seulement manipulable (au mini dans un BYTE de 8 bits) et ensuite on peut adresser ce conteneur.