Implémentation crible erastothene

Le
Olivier BURELLI
Bonjour,

je souhaiterai avoir votre avis sur mon implémentation du crible
d'Erastothène.

Mon code met 9 minute pour fournir la liste des nombres premier sur
l'intervalle [2, 10 000 000]

voici le lien du source : http://codepad.org/5CXy0oLS

sur l'intervalle [2, 120] celui-ci semble correct.

mon algo est-il bon ?
Le code, au niveau de la vitesse de calcul peut il être amélior=
é ?

Vaut il mieux pour créer un second vector nombres_premier où sto=
cker
les nombres premier trouvé pour effectuer les divers traitements
possible sur un vector de taille forcement moindre ?

Comment puis-je mesurer ce genre de problèmatique, sur un plan
efficacité ?


Vous remerciant par avance,

Cdt,

Olivier.
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 2
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Pascal J. Bourguignon
Le #23525691
Olivier BURELLI
je souhaiterai avoir votre avis sur mon implémentation du crible
d'Erastothène.

Mon code met 9 minute pour fournir la liste des nombres premier sur
l'intervalle [2, 10 000 000]

voici le lien du source : http://codepad.org/5CXy0oLS

sur l'intervalle [2, 120] celui-ci semble correct.

mon algo est-il bon ?
Le code, au niveau de la vitesse de calcul peut il être amélioré ?



Au niveau de la vitesse de calcul, tu pourrais ramener les doigts dans
le nez, en utilisant un compilateur lisp ciblant une machine virtuelle,
(et en perdant un peu de temps dans un ramassage de miettes), à deux
secondes et demi sur mon i7:

CL-USER> (time (defvar *primes* (COM.INFORMATIMAGO.COMMON-LISP.ARITHMETIC.PRIMES:COMPUTE-PRIMES-TO 10000000)))
Real time: 2.53821 sec.
Run time: 2.536615 sec.
Space: 5942648 Bytes
GC: 1, GC time: 0.010998 sec.
*PRIMES*
CL-USER>

https://gitorious.org/com-informatimago/com-informatimago/blobs/master/common-lisp/arithmetic/primes.lisp

(Bien sur, si j'utilisais un compilateur lisp générant du code natif
bien optimisé, ça pourrait aller encore plus vite).


Vaut il mieux pour créer un second vector nombres_premier où stocker
les nombres premier trouvé pour effectuer les divers traitements
possible sur un vector de taille forcement moindre ?



Il vaut mieux programmer dans un langage de plus haut niveau. Ça laisse
l'esprit plus libre pour trouver de meilleurs algorithmes.



Comment puis-je mesurer ce genre de problèmatique, sur un plan
efficacité ?



En profilant. Voir gcov, gprof, etc.



Le principal problème dans ton code, c'est la ligne 43, qui incrémente j
seulement de 1. Donc, après 3, tu vas chercher à éliminer les multiples
de 4, or ils ont déjà été éliminés en tant que multiples de 2, etc.

Similairement, ligne 30, il n'y a aucune raison de cribler tous les
entiers, puisque seuls les nombres supérieurs à j peuvent être un
multiple de j.



En fin de compte tu n'as pas implémenté le crible d'Ératosthène, puisque
ton algorithme consiste à diviser systématiquement tous les entiers par
tous les entiers.

Fais une recherche google sur crible d'Ératosthène, et regarde les
images ou les vidéo démontrant son fonctionnement. Par exemple, sur
http://fr.wikipedia.org/wiki/Crible_d%27%C3%89ratosth%C3%A8ne
Pour supprimer de la liste les multiples de p, on n'a pas besoin de
diviser par p, il suffit de cocher bêtement une case sur p.

--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.
Fabien LE LEZ
Le #23525781
On Sun, 03 Jul 2011 01:55:29 +0200, "Pascal J. Bourguignon"

lisp



Oui, on sait, Lisp est mieux que tout le reste.
Note toutefois que fr.comp.lang.c++ est un groupe dédié au C++.
Fabien LE LEZ
Le #23525801
On Sun, 3 Jul 2011 00:31:59 +0000, Olivier BURELLI

je souhaiterai avoir votre avis sur mon implémentation du crible
d'Erastothène.



La deuxième partie du message de Pascal est pertinente.

Le principe du crible : tous les nombres de 2 à N sont considérés
comme premiers, et on enlève l'indicateur "premier" à une bonne partie
des nombres, au fur et à mesure du crible.

À priori, le conteneur adéquat serait donc un vector<bool>, contenant
au départ N fois "true" (sauf pour 0 et 1), et passage à "false" pour
tous les multiples.

La boucle (version "naïve") :

vector<bool> v (N, true);

n=2
v[2]==true => 2 est un nombre premier. On peut l'afficher
immédiatement.
On enlève tous les multiples : v[4]= false; v[6]= false; etc.

n=3
v[3]==true => 3 est un nombre premier. On l'affiche, et on enlève tous
les multiples.

n=4
v[4]=úlse => 4 n'est pas premier. On passe.

etc.
Olivier BURELLI
Le #23525851
Le Sun, 03 Jul 2011 01:55:29 +0200,
"Pascal J. Bourguignon"

> voici le lien du source : http://codepad.org/5CXy0oLS

Le principal problème dans ton code, c'est la ligne 43, qui
incrémente j seulement de 1. Donc, après 3, tu vas chercher à
éliminer les multiples de 4, or ils ont déjà été éliminés en tant que
multiples de 2, etc.




J'ai justement évité le pb avec la boucle while :

// Iterer tant que le plus petit nombre premier trouvé
// est inférieur a SQRT(borne maximale)
while (j < sqrt(m))


Similairement, ligne 30, il n'y a aucune raison de cribler tous les
entiers, puisque seuls les nombres supérieurs à j peuvent à ªtre un
multiple de j.



serait-il préférable d'initialiser la seconde boucle ainsi ?

// Parcourir le vector
for (unsigned long int i= j + 1; i < entiers.size(); ++i)
{

et de supprimer le test devenant inutile
// ne pas éliminer la valeur j
if (entiers[i] > j)



En fin de compte tu n'as pas implémenté le crible d'Ératos thène,
puisque ton algorithme consiste à diviser systématiquement tous les
entiers par tous les entiers.



je pensais l'avoir effectué, je vais le recompiler en mettant un
compteur de boucle et afficher celles-ci.

Mais la boucle while respectait la condition selon moi.

Fais une recherche google sur crible d'Ératosthène, et regarde les
images ou les vidéo démontrant son fonctionnement. Par exemple , sur
http://fr.wikipedia.org/wiki/Crible_d%27%C3%89ratosth%C3%A8ne
Pour supprimer de la liste les multiples de p, on n'a pas besoin de
diviser par p, il suffit de cocher bêtement une case sur p.



j'elimine les entiers en mettant la valeur 0 dans le vector tant que
le plus petit entier trouvé est inferieur a SQRT(borne max).


Merci beaucoup pour tes remarques.

Cdt,

Olivier.
Olivier BURELLI
Le #23525891
Le Sun, 03 Jul 2011 07:02:54 +0200,
Fabien LE LEZ

Le principe du crible : tous les nombres de 2 à N sont considér és
comme premiers, et on enlève l'indicateur "premier" à une bonne partie
des nombres, au fur et à mesure du crible.




Il me semble bien que mon code y réponde.

À priori, le conteneur adéquat serait donc un vector<bool>, con tenant
au départ N fois "true" (sauf pour 0 et 1), et passage à "false " pour
tous les multiples.
La boucle (version "naïve") :

vector<bool> v (N, true);

n=2
v[2]==true => 2 est un nombre premier. On peut l'afficher
immédiatement.
On enlève tous les multiples : v[4]= false; v[6]= false; etc.

n=3
v[3]==true => 3 est un nombre premier. On l'affiche, et on enlà ¨ve tous
les multiples.

n=4
v[4]=úlse => 4 n'est pas premier. On passe.




Huumm le code suivant réalise exactement la même chose non ?

// Crible
// Partir du premier nombre premier

unsigned long int j=2;

// Iterer tant que le plus petit nombre premier trouvé
// est inférieur a SQRT(borne maximale)

while (j < sqrt(m))
{
// Parcourir le vector
for (unsigned long int i=0; i < entiers.size(); ++i)
{
// ne pas éliminer la valeur j
if (entiers[i] > j)
{
// tester si l'entier est divisible.
if (entiers[i] % j == 0)
{
entiers[i]=0; // Le marquer
}
}
}

++j;
}


Merci pour vos remarques.


Cdt,

Olivier.
espie
Le #23526311
In article Olivier BURELLI
// Crible
unsigned long int j=2;

// Tant que le plus petit nombre premier trouvé < SQRT(borne maximale)
while (j <= sqrt(m))
{

// Parcourir le vector des entiers premiers (entiers[j] !=0 )
if(entiers[j] != 0)
{
for (unsigned long int i=0;i < entiers.size(); ++i)
{
// ne pas éliminer la valeur j = entiers[i]
if (entiers[i] > j )
{
// tester si l'entier est divisible.
if(entiers[i] % j == 0)
{
entiers[i]=0; // L'éliminer
}
}
}
}
++j;
}


J'ai pris en compte vos remarques, et je pense que ce code correspond
au crible d'Erastothène.



Ben non, toujours pas. Il n'y a pas de division dans un vrai crible
d'erathosthene. Regarde ta boucle interieure, c'est du grand n'importe
quoi. C'est pourtant pas dur d'ecrire quelque chose genre:

for(unsigned int i = 2 * j; i < entier.size(); i += j)
entiers[i] = 0;

Accessoirement, tu n'as aucune garantie que ton compilo va determiner que
sqrt(m) est une constante et l'optimiser. Il vaut mieux garder au chaud
la partie entiere de sa valeur pour eviter tout souci, e.g.,
const unsigned int bound = sqrt(m)
Fabien LE LEZ
Le #23526491
On Sun, 3 Jul 2011 08:33:04 +0000, Olivier BURELLI

Huumm le code suivant réalise exactement la même chose non ?



Non.

Ton code tente la division de chaque i par chaque j. En gros, c'est
l'implémentation naïve de la détection de nombres premiers.

Le crible saute automatiquement les non-premiers, et n'effectue que
des multiplications.
Grosso modo, si tu as une division dans ton code (ou un modulo, ce qui
revient au même), il ne s'agit pas du crible.
Pascal J. Bourguignon
Le #23526541
Olivier BURELLI
Huumm le code suivant réalise exactement la même chose non ?

// Crible
// Partir du premier nombre premier

unsigned long int j=2;

// Iterer tant que le plus petit nombre premier trouvé
// est inférieur a SQRT(borne maximale)

while (j < sqrt(m))



Nombre de boucles: sqrt(m) (à cause du j++)

// Parcourir le vector
for (unsigned long int i=0; i < entiers.size(); ++i)



Nombre de boucles: sqrt(m)*entiers.size()

// ne pas éliminer la valeur j
if (entiers[i] > j)
{



Nombre de boucles: sqrt(m)*entiers.size()
+ nombre de tests: sqrt(m)*entiers.size()

// tester si l'entier est divisible.
if (entiers[i] % j == 0)



Nombre total de boucles: sqrt(m)*entiers.size()
+ nombre total de tests: sqrt(m)*(2*entiers.size()-j)
+ nombre total de divisions: sqrt(m)*(entiers.size()-j)

entiers[i]=0; // Le marquer





(while (< cur-prime n)

;; nombre de boucles: nombre de premiers < n (voir ci-dessous)

(setq bit (+ cur-prime (/ (- cur-prime 3) 2)))

(while (< bit bits-max)
(setf (aref bits bit) 0)
(incf bit cur-prime)
;; Nombre de boucles (n - cur-prime)/cur-prime
;; nombre de tests: 0 (à part celui de la boucle)
;; nombre de divisions: 0
)

;; Ici on recherche le premier suivant O(next-prime - cur-prime)
;; ce qui fait que la boucle principale n'est exécutée qu'une fois pour
;; chaque premier.
(setq bit (1+ (/ (- cur-prime 3) 2)))
;; search next prime
(setq bit (position 1 bits :start bit))
(if bit
(setq cur-prime (+ bit bit 3)
prime-count (1+ prime-count))
(setq cur-prime n)))

Le nombre total de boucles interne sera donc
p<n p<n
Σ (n-p)/p = n Σ 1/p ≈ n log(n)
p premier p premier

ce qui est bien moindre que n√n.


--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.
Fabien LE LEZ
Le #23526651
On Sun, 3 Jul 2011 00:31:59 +0000, Olivier BURELLI

Mon code met 9 minute pour fournir la liste des nombres premier sur l'intervalle [2, 10 000 000]



Pour référence :
Je viens d'implémenter un crible en quelques lignes.
Sur un Core2 Duo 1,8 GHz, il met un peu moins d'une seconde pour
calculer les nombres premiers jusqu'à dix millions, et onze secondes
pour calculer les nombres premiers jsuqu'à cent millions.
espie
Le #23526641
In article Fabien LE LEZ
On Sun, 3 Jul 2011 08:33:04 +0000, Olivier BURELLI

Huumm le code suivant réalise exactement la même chose non ?



Non.

Ton code tente la division de chaque i par chaque j. En gros, c'est
l'implémentation naïve de la détection de nombres premiers.

Le crible saute automatiquement les non-premiers, et n'effectue que
des multiplications.



des additions... il n'y a meme pas de multiplication dans le crible
d'erathosthene implemente correctement, ce qui est vachement interessant
pour sa perf.
Publicité
Poster une réponse
Anonyme