CACUL (RAPIDE) DE PGCD
cs_max12
Messages postés
1491
Date d'inscription
dimanche 19 novembre 2000
Statut
Modérateur
Dernière intervention
7 juillet 2014
-
3 nov. 2007 à 06:28
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019 - 9 déc. 2007 à 18:05
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019 - 9 déc. 2007 à 18:05
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/44591-cacul-rapide-de-pgcd
https://codes-sources.commentcamarche.net/source/44591-cacul-rapide-de-pgcd
9 déc. 2007 à 18:05
JCDjcd > une proposition:
- on passe pow2 en DWORD.
- init: pow2 = 0;
- dans la boucle, pow2 <<= 1; devient pow2++;
- on sort avec: return (a << pow2); au lieu de: return pow2*a;
Sur grands entiers, dans la boucle on gagnera la série de SHLD nécessaire pour faire un <<. Sur des 64 bits on devrait gagner peu mais sur du 512 ou plus, le benef deviendra conséquent car pour faire un << il faut un SHL plus ((sizeNbr - 32) / 32) fois SHLD, ça devient vite très couteux.
9 déc. 2007 à 17:01
par contre l'utilisation du pow est scandaleuse, car que viennent faire les doubles la dedans ? RIEN, alors plutot faire return (1<<k)*b; c'est mieux
8 déc. 2007 à 17:17
/**
* Calcul le "Plus Grand Commun Diviseur" de a et b
* grâce à l'algorithme binaire
*
* @param a un entier positif
* @param b un entier positif
* @return le PGCD(a,b)
*/
unsigned int pgcdC( unsigned int a, unsigned int b )
{
int t;
double k = 0;
// Trouve la puissance de 2
while( !(a&1) && !(b&1) )
{
k++;a >>1; // a a/2b >>1; // b b/2
}
// Si a est impairif( !(a&1) ) t -b; else t a;
while( t != 0 )
{
// Tant que t est pair
while( !(t&1) ) t >>1; // t t/2
if (t > 0) a t; else b -t;
t = a - b;
}
return (unsigned int)pow(2,k)*b; // 2^k*b
}
5 nov. 2007 à 12:00
Bravo !
3 nov. 2007 à 06:28
A+