Sujet Précédent Sujet Suivant

CRIBLE D'ERATOSTHÈNE OPTIMISÉ

pgl10 Messages postés 364 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 2 mars 2023 - 27 juin 2011 à 14:21
LeFauve42 Messages postés 239 Date d'inscription vendredi 20 octobre 2006 Statut Membre Dernière intervention 20 avril 2009 - 14 nov. 2011 à 10:52

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

pgl10 Messages postés 364 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 2 mars 2023 9
27 juin 2011 à 14:21

Il y a un moyen simple de faire le calcul plus rapidement. Dans le programme ici présenté on met au départ un indicateur à 1 pour tous les nombres entiers impairs et ensuite on marque à 0 tous les nombres composés impairs. Que se passerait-il si on ne marquait pas les multiples de 3 ? Le nombre 45, par exemple, ne serait plus marqué en tant que composé comme multiple de 3 mais il le serait en tant que multiple de 5. Au final seuls les nombres en 3^n resteraient avec un indicateur à 1 Mais si on en tient compte au début de prem() en ajoutant : if(i==3) return true; if(i%3==0) return false; après les 2 lignes semblables pour 2 on rétablit un calcul correct. Il y a seulement un ralentissement faible de prem() mais on évite le marquage de nombreux entiers, ce qui gagne du temps. Ceci permet de passer de 43.071 sec à 41.161 sec pour 100000000.bat et de 95.050 sec à 90.765 sec pour maximum.bat Et puis on peut continuer. Si on évite de marquer les multiples de 3, 5, 7, 11 et 13 en commençant à 17 on obtient 36.247 sec pour 100000000.bat et 80.823 sec pour maximum.bat Alors, voilà ! Est-ce que l'on peut encore parler d'algorithme d'Eratosthène ? Est-ce acceptable ? C'est à chacun de décider si on peut faire cette modification.

pgl10 Messages postés 364 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 2 mars 2023 9
27 juin 2011 à 21:23

Il y a bien un autre gain de temps facile. Dans la boucle : for(i=5; i<m; i=i+s) on peut remplacer le : if(prem(i)) par : q=i>>4; r=... if(...) comme dans prem(i). Cela évite l'appel à la fonction prem() et les 3 if du début de prem() qui sont inutiles à cet endroit. Mais le gain est petit et presque insignifiant, parce que la boucle externe en i est moins fréquente que la boucle interne en j.

Rescassol Messages postés 10 Date d'inscription samedi 14 février 2004 Statut Membre Dernière intervention 2 octobre 2011
4 juil. 2011 à 07:07

Voilà qui me semble plus rapide (en C++), avec une table qui s'auto-remplit:

const long NMAX = 1000000L;

vector <long> prem, sigma;

bool premier(long n)
{
for (long k = 0; prem[k] * prem[k] <= n; k++) if (n % prem[k] == 0) return false;

return true;
}

void FaireTable(void)
{
prem.push_back(2);
for (long n = 2; n < NMAX; n++)
if (premier(n))
prem.push_back(n);
}

Rescassol Messages postés 10 Date d'inscription samedi 14 février 2004 Statut Membre Dernière intervention 2 octobre 2011
4 juil. 2011 à 07:17

Rectification (si on pouvait modifier son propre message, ce serait bien) :

const long NMAX = 1000000L;

vector <long> prem;

bool premier(long n)
{
for (long k = 0; prem[k] * prem[k] <= n; ++k) if (n % prem[k] == 0) return false;

return true;
}

void FaireTable(void)
{
prem.push_back(2);
for (long n = 3; n < NMAX; n += 2)
if (premier(n))
prem.push_back(n);
}

LeFauve42 Messages postés 239 Date d'inscription vendredi 20 octobre 2006 Statut Membre Dernière intervention 20 avril 2009
4 juil. 2011 à 12:56

La seule optimisation vraiment efficace du cribble consiste a sauter les premieres iterations et a initialiser le tableau de maniere efficace.
Pourquoi ne pas deplier la boucle jusqu'a ce que les valeurs s'alignent sur un multiple de 8, et remplir tout ca avec des _int64 ?
La derniere fois que j'ai joue avec ca (sur un 68030 a 25 MHz :o) ), 7 etait le nombre magique (au dela duquel on ne gagnait plus grand chose a precalculer le tableau de crible).
Il doit aussi y avoir des modes d'adressage en assembleur permettant d'accelerer sans commune mesure le traitement par rapport a ce qui peut se faire en C (par exemple, sur les 68030, on peut recuperer en une instructuion machine le premier bit a 0 en memoire a partir d'une adresse donnee. Je serais etonne que les intels modernes n'aient pas cette possibilite)