Implémentation crible erastothene

Le Sun, 3 Jul 2011 08:20:33 +0000,
Olivier BURELLI <olivier@burelli.fr> a écrit :

Le Sun, 03 Jul 2011 01:55:29 +0200,
"Pascal J. Bourguignon" <pjb@informatimago.com> a écrit :


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

> 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'Érat osthène,
> puisque ton algorithme consiste à diviser systématiquement to us 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.

Effectivement, mon code criblait quand même la valeur 4.

J'ai donc rajouté une condition. Je gagne 8 minutes... :)

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

Merci beaucoup.

cordialement,

Olivier.

In article <87ei27prg4.fsf@kuiper.lan.informatimago.com>,
Pascal J. Bourguignon <pjb@informatimago.com> wrote:

Olivier BURELLI <olivier@burelli.fr> writes:

[du C++ un peu buggue]

[du Lisp]

Okay, la, je craque. Pascal, tu as un debutant qui a deja du mal avec
ce qu'il est en train de faire. Tu crois que ca sert vraiment a quelque
chose de lui montrer du code lisp ? c'est pas reellement le bon moment pour
le convaincre, et c'est totalement hors sujet pour le newsgroup.

Je peux aussi ressortir l'implementation du crible pour le jeu de la vie,
c'est vachement joli, ca marche super bien, ... et ca ne va pas non plus
faire avancer le sujet.

On Sun, 3 Jul 2011 11:06:34 +0000 (UTC), espie@lain.home (Marc Espie):

des additions... il n'y a meme pas de multiplication dans le crible
d'erathosthene implemente correctement

En effet. Le pire, c'est que je viens de l'implémenter (pour mesurer
les perfs), et qu'il n'y a effectivement pas de multiplications. Je
suis plus doué pour programmer que pour en parler :-/

Fabien LE LEZ <gramster@gramster.com> writes:

On Sun, 3 Jul 2011 00:31:59 +0000, Olivier BURELLI
<olivier@burelli.fr>:

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.

Après, on peut jouer sur la bit map. Par exemple, aucun nombre pair
n'est un nombre premier (à part 2 bien sur), on peut éviter d'allouer un
bit sur deux. On peut aussi éliminer un bit sur trois en évitant
d'allouer des bits pour les multiples de 3. Etc. Mais la fonction pour
convertir entre les index de bit et les nombres va vite devenir
compliquée. Ma fonction compute-primes-to se contente d'utiliser un bit
pour chaque impair.

--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.

espie@lain.home (Marc Espie) writes:

In article <87ei27prg4.fsf@kuiper.lan.informatimago.com>,
Pascal J. Bourguignon <pjb@informatimago.com> wrote:

Olivier BURELLI <olivier@burelli.fr> writes:

[du C++ un peu buggue]

[du Lisp]

Okay, la, je craque. Pascal, tu as un debutant qui a deja du mal avec
ce qu'il est en train de faire. Tu crois que ca sert vraiment a quelque
chose de lui montrer du code lisp ? c'est pas reellement le bon moment pour
le convaincre, et c'est totalement hors sujet pour le newsgroup.

Je peux aussi ressortir l'implementation du crible pour le jeu de la vie,
c'est vachement joli, ca marche super bien, ... et ca ne va pas non plus
faire avancer le sujet.

C'est une question d'algorithme, est lisp est un langage algorithmique,
aussi bon qu'un autre pour décrire un algorithme. (Meilleur en fait,
pour la raison que j'ai indiquée).

Knuth décrit ses algorithmes en assembleur, tu aurais peut être préféré
que je fasse de même?


--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.

Le Sun, 3 Jul 2011 09:27:13 +0000 (UTC),
espie@lain.home (Marc Espie) a écrit :

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;

Effectivement, je pensais par multiple : i%j != 0.

Mais sincerement, je ne pense pas que j'aurai pu traduire :

pour chaque muliple de j, affecter zero, par cette boucle :

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


bref, il me faut travailler ma réflexion pour produire de bons
algorithmes.
Pour moi, oui c'était dur... :p

Merci beaucoup.

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)

Oui, ne pas usiter de constantes magiques.


Encore merci,

Cdt,

Olivier.

Le Sun, 03 Jul 2011 13:27:10 +0200,
"Pascal J. Bourguignon" <pjb@informatimago.com> a écrit :

C'est une question d'algorithme, est lisp est un langage
algorithmique, aussi bon qu'un autre pour décrire un algorithme.
(Meilleur en fait, pour la raison que j'ai indiquée).

Knuth décrit ses algorithmes en assembleur, tu aurais peut être
préféré que je fasse de même?

Oui Stop plizz, sinon je vais sortir ma becane et faire un tour... :p

Je ne fais effectivement qu'un exercice demande par mon livre
d'apprentissage du C++.

Pas du LISP, au pire, je vais chercher un PB 15(automate), ou je cable
du pneumatique...

Néanmoins pascal tes conseils m'ont éclairé.

L'auteur demandait de trouver l'algo sur le net...

je n'ai trouvé que le principe, essayé de l'implémenter, n'y suis
pas arrivé...

Au final, marc a fourni un algo juste, simple et efficace, je le
réetudierai à tête reposée. Ainsi, dans l'avenir j'util iserai une
boucle correctement.

Une chose est sure, je vais en parallèle ouvrir mon bouquin d'algo... :p


Merci beaucoup à vous tous.


cdt,

Olivier.

Olivier BURELLI <olivier@burelli.fr> writes:

Le Sun, 03 Jul 2011 13:27:10 +0200,
"Pascal J. Bourguignon" <pjb@informatimago.com> a écrit :

C'est une question d'algorithme, est lisp est un langage
algorithmique, aussi bon qu'un autre pour décrire un algorithme.
(Meilleur en fait, pour la raison que j'ai indiquée).

Knuth décrit ses algorithmes en assembleur, tu aurais peut être
préféré que je fasse de même?

Oui Stop plizz, sinon je vais sortir ma becane et faire un tour... :p

Je ne fais effectivement qu'un exercice demande par mon livre
d'apprentissage du C++.

Pas du LISP, au pire, je vais chercher un PB 15(automate), ou je cable
du pneumatique...

Néanmoins pascal tes conseils m'ont éclairé.

L'auteur demandait de trouver l'algo sur le net...

je n'ai trouvé que le principe, essayé de l'implémenter, n'y suis
pas arrivé...

Au final, marc a fourni un algo juste, simple et efficace, je le
réetudierai à tête reposée. Ainsi, dans l'avenir j'utiliserai une
boucle correctement.

Une chose est sure, je vais en parallèle ouvrir mon bouquin d'algo... :p

Mais je t'avais donné l'url de l'algo en premier.

Que l'algorithme soit écrit en javanais, en lisp ou en java, ça n'a
aucune importance. Mais le mieux, clairement, c'est que l'algorithme soit
écrit dans un langage algorithmique, plutôt que dans un langage naturel.

D'un autre côté, il est aussi important que l'algorithme ne soit pas
écrit dans un langage de trop bas niveau, car alors il incorpore des
détails qui ne sont pas pertinents (par exemple, gestion de la mémoire,
taille des entiers, etc).


--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.

In article <87liwfo3ae.fsf@kuiper.lan.informatimago.com>,
Pascal J. Bourguignon <pjb@informatimago.com> wrote:

D'un autre côté, il est aussi important que l'algorithme ne soit pas
écrit dans un langage de trop bas niveau, car alors il incorpore des
détails qui ne sont pas pertinents (par exemple, gestion de la mémoire,
taille des entiers, etc).

PARDON ? Pas pertinent ?

Si tu veux analyser le crible d'erathosthene, il faut ABSOLUMENT voir quelle
place il prend, et quelle taille font les entiers. Je dirais meme plus: le
crible est un exemple de choix pour illustrer les compromis temps/place prise
que tu peux utiliser sur un algo.

Un petit saut sur wikipedia confirme, O(n) place et O(n(log n)(log log n))
temps.

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Tiens, d'ailleurs, j'y remarque qu'on peut commencer a j * j, puisque de
facon evidente tout ce qui est avant a disparu.

Il y a aussi un lien vers un article qui decrit une version fortement
plus efficace...

espie@lain.home (Marc Espie) writes:

In article <87liwfo3ae.fsf@kuiper.lan.informatimago.com>,
Pascal J. Bourguignon <pjb@informatimago.com> wrote:

D'un autre côté, il est aussi important que l'algorithme ne soit pas
écrit dans un langage de trop bas niveau, car alors il incorpore des
détails qui ne sont pas pertinents (par exemple, gestion de la mémoire,
taille des entiers, etc).

PARDON ? Pas pertinent ?

Je m'attendais à une autre question, à savoir définir un algorithme.
Et la réponse que je me préparais à donner permet justement d'expliciter
ce qui n'est pas pertinent.

Un algorithme, c'est une fonction scheme sans aucune variable libre.

On pourrait donner une définition équivalente pour Common Lisp, mais ce
serait un peu plus long car Common Lisp est un lisp-1.


(define crible
(lambda (n ; l'entier maximum à tester.
+ ; operation +
< ; operation <
make-vector ; ...
vector-ref
vector-set
; ...
)

...))

Ainsi, on documente clairement ce qui fait partie de l'algorithme
(l'expression dans le corps de la fonction) et ce qui n'en fait pas, et
donc, dont la complexité est ignorée (mais qui sont utilisés comme
facteurs dans le calcul de la complexité de l'algorithme.

Ainsi on voit directement que pour comparer un algorithme qui utilise +
avec un algorithme qui utilise /, il faut les ramener à des algorithmes
utilisant -:

(lambda (n - < ...)
(crible-+ n
(lambda (a b) (- a (- 0 b))) ; +, O(1) en -
...))
vs.

(lambda (n - < ...)
(crible-/ n
(lambda (a b)
...) ; /, entre O(nlogn) et O(n²) en -,
; selon l'algorithme choisi
...))

Si tu veux analyser le crible d'erathosthene, il faut ABSOLUMENT voir quelle
place il prend, et quelle taille font les entiers. Je dirais meme plus: le
crible est un exemple de choix pour illustrer les compromis temps/place prise
que tu peux utiliser sur un algo.

En général, on ignore totalement le problème de la taille des nombres
eux-mêmes dans les algorithmes. C'est un paramètre qui n'entre pas en
ligne de compte: on ne compte que le nombre d'opérations "élémentaires",
sans tenir compte de la différence que leur paramètres peuvent
impliquer. Mais on peut aussi réifier cet aspect, en utilisant des
primitives de plus bas niveau. Ainsi au lieu d'avoir:

(lambda (...
integer-vector-ref
integer-vector-set
...)
...)

on peut utiliser:

(lambda (...
8bit-vector-ref
8bit-vector-set
...)
...)

ou bien sur, 16bit or 32bit. Mais comme je l'ai dit, en général les
algorithmes n'entrent pas dans ces considérations de bas niveau.

C ou C++ nous y obligent, en nous faisant choisir entre char, short ou
int, et c'est bien là le problème, car en général, ce n'est pas une
considération.

Par exemple, dans le cas du crible d'Ératosthène, le paramètre, c'est le
nombre entier maximum. Ce n'est pas la taille maximum des entiers que
l'on crible. (D'accord, il y a une relation, mais le fait que log₂(n)
n'est jamais calculé prouve ce que je dis).


Donc, toute la question c'est de savoir quelles sont les opérations
élémentaires pertinentes.

Est ce que eliminer-les-multiples-de est une operation élémentaire?
(Pour certains énoncés du crible, on le dirait effectivement).

Est ce que c'est la manipulation d'un bit en mémoire qui l'est?
(Pour certains langages de programmations, on le dirait aussi).

La réponse, c'est que ça dépend de l'algorithme en question, d'où la
nécessité d'expliciter toutes les opérations "élémentaires" utilisées.

Un petit saut sur wikipedia confirme, O(n) place et O(n(log n)(log log n))
temps.

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Tiens, d'ailleurs, j'y remarque qu'on peut commencer a j * j, puisque de
facon evidente tout ce qui est avant a disparu.

Il y a aussi un lien vers un article qui decrit une version fortement
plus efficace...

--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.