CRIBLE D'ERATOSTHÈNE OPTIMISÉ

Signaler
Messages postés
329
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
7 octobre 2021
-
Messages postés
239
Date d'inscription
vendredi 20 octobre 2006
Statut
Membre
Dernière intervention
20 avril 2009
-
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/53321-crible-d-eratosthene-optimise

Messages postés
239
Date d'inscription
vendredi 20 octobre 2006
Statut
Membre
Dernière intervention
20 avril 2009

Saros, tout ca remonte à plus de 20 ans, alors mes souvenirs sont peut-etre un peu rouillés :o)

Le truc était qu'avec la méthode utilisée (le 68030 avait 2 instructions bien pratiques pour le cribble qui en gros pouvaient :
- Fixer le bit "n" à partir d'une adresse (n étant sur 32 bits, pas juste <8 (ou a 64))
- Trouver le premier bit à un (ou a zero, je ne me rappelle plus très bien) à partir d'une adresse donnée) ce qui était lent c'était les premières itérations.

Les 7 premières en particulier (à moins que ce ne soit jusqu'à celle du chiffre 7).

Donc, on les précalcule, et on initialise le tableau avec cette valeur.
Pour aller encore plus vite, au lieu de remplir la partie minimale de la boucle à chaque iteration, j'avais pris plusieurs fois cette partie de n octets jusqu'à obtenir un multiple de 4 afin d'utiliser uniquement des MOVE sur 32 bits, bien plus rapides que les MOVE sur 8 bits.

Ici il faudra aligner sur un multiple de 8 pour faire un move sur 64 bits.

Je ne suis pas sur que ce soit très clair, mais si tu essaies ca devrait etre plus facile à comprendre :o)
Messages postés
921
Date d'inscription
vendredi 20 décembre 2002
Statut
Membre
Dernière intervention
23 septembre 2010

Ça peut être intéressant de savoir jusqu'à quand il faut déplier la boucle en fonction de la borne !
LeFauve42 le chiffre de 7 que tu as avancé c'était pour calculer les nombres premiers jusqu'à combien ?
Messages postés
329
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
7 octobre 2021
2
Cette variante utlilisant les __int64 est en ligne sur mon site web : http://pgl10.chez.com avec source, exécutable, exemples et documentation.
Messages postés
329
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
7 octobre 2021
2
Remerciements tardifs à Rescassol et LeFauve42 ( J'étais en déplacement sans accès à Internet ) Avec une variante utlilisant les __int64 j'ai pu effectivement calculer les 1300005926 nombres premiers entre 1 et 30 milliards. Au-delà il faut une autre gestion de la mémoire pour les indicateurs : nombre premier ou nombre composé.
Afficher les 9 commentaires