pgl10
Messages postés380Date d'inscriptionsamedi 18 décembre 2004StatutMembreDernière intervention29 octobre 2023
-
27 juin 2011 à 14:21
LeFauve42
Messages postés239Date d'inscriptionvendredi 20 octobre 2006StatutMembreDernière intervention20 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.
LeFauve42
Messages postés239Date d'inscriptionvendredi 20 octobre 2006StatutMembreDernière intervention20 avril 2009 14 nov. 2011 à 10:52
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)
Saros
Messages postés921Date d'inscriptionvendredi 20 décembre 2002StatutMembreDernière intervention23 septembre 2010 14 nov. 2011 à 01:32
Ç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 ?
pgl10
Messages postés380Date d'inscriptionsamedi 18 décembre 2004StatutMembreDernière intervention29 octobre 202311 18 juil. 2011 à 09:11
Cette variante utlilisant les __int64 est en ligne sur mon site web : http://pgl10.chez.com avec source, exécutable, exemples et documentation.
pgl10
Messages postés380Date d'inscriptionsamedi 18 décembre 2004StatutMembreDernière intervention29 octobre 202311 14 juil. 2011 à 19:58
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é.
LeFauve42
Messages postés239Date d'inscriptionvendredi 20 octobre 2006StatutMembreDernière intervention20 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)
Rescassol
Messages postés10Date d'inscriptionsamedi 14 février 2004StatutMembreDerniè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);
}
Rescassol
Messages postés10Date d'inscriptionsamedi 14 février 2004StatutMembreDerniè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);
}
pgl10
Messages postés380Date d'inscriptionsamedi 18 décembre 2004StatutMembreDernière intervention29 octobre 202311 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.
pgl10
Messages postés380Date d'inscriptionsamedi 18 décembre 2004StatutMembreDernière intervention29 octobre 202311 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.
14 nov. 2011 à 10:52
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)
14 nov. 2011 à 01:32
LeFauve42 le chiffre de 7 que tu as avancé c'était pour calculer les nombres premiers jusqu'à combien ?
18 juil. 2011 à 09:11
14 juil. 2011 à 19:58
4 juil. 2011 à 12:56
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)
4 juil. 2011 à 07:17
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);
}
4 juil. 2011 à 07:07
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);
}
27 juin 2011 à 21:23
27 juin 2011 à 14:21