Encore une source sur le PGCD...
c'est bon on le connait par coeur...
cette source sera supprimee...
Pas trop vite mes amis !
Je propose trois algorithmes :
- le stupide : PGCD(a,b)=PGCD(a-b,b)
- le scolaire : PGCD(a,b)=PGCD(a%b,b)
- le rapide, la nouveaute
cette source a pour but justement de presenter cet
algorithme...
La comparaison a ete faites, le resultat dans la capture d'ecran
Le principe est simple :
l'algorithme est efficace et ne traite que les nombres impairs,
on peut toujours s'y ramenner en calculant toutes les puissances
de deux en commun aux deux nombres...
apres on applique la methode "stupide" qui repose sur le fait que
PGCD(a,b)=PGCD(a-b,b), or puisque a et b sont impairs, a-b est pair,
donc on peut enlever toutes les puissances de 2 a a-b car on sait
qu'elles n'interviendrons pas dans le PGCD de deux nombres impairs,
ceci permet de dimunuer drastiquement le nombre d'operations !
puisque l'on divise a chaque etape au moins un des deux nombres par
deux...
On voit que cet algorithme est efficace sur des grands nombres,
a partir de nombres a 45bits, il devient le plus rapide...
De plus je ne parle pas ici du cout temporel de l'operation % dans
l'algorithme scolaire, il est a cout constant... alors que cet algorithme
n'effectue QUE des comparaisons, des soustractions et des divisions par deux !
ce qui a un cout temporel lineaire si on utilise les librairies de
grands nombres, alors que le % n'est plus a cout constant,
donc cet algorithme est beaucoup, beaucoup mieux !!!!
Source / Exemple :
//==========================================================================
// ENTIERS 64 BITS
//==========================================================================
typedef unsigned __int64 U64;
//==========================================================================
// PGCD
//==========================================================================
U64 pgcdStupid(U64 a,U64 b)
{
while(1) // boucle infinie
{
if(b > a) // on veut toujours avoir <a> plus grand que <b>
{
U64 tmp;
tmp = a;
a = b;
b = tmp;
}
if(0==b) break; // bingo ! PGCD(a,0) = a
a -= b;
}
return a;
} // pgcdStupid()
//--------------------------------------------------------------------------
U64 pgcdSchool(U64 a,U64 b)
{
if(b==0) return a; // cas trivial ... PGCD(a,0)=a
while(1) // boucle infinie
{
U64 r;
r = a%b;
if(0==r) break; // bingo ! PGCD(a=k.b,b)=b
// PGCD(a,b)=PGCD(b,r=a%b)
a = b;
b = r;
}
return b;
} // pgcdSchool()
//--------------------------------------------------------------------------
U64 pgcdFast(U64 a,U64 b)
{
U64 pow2;
// cas trivial ... PGCD(a,0)=a ou PGCD(0,b)=b
// dans les deux cas : PGCD(a,b)=a+b si l'un des deux nombres est nul
if(0==a || b==0) return a+b;
// on s'occupe de toutes les puissances de deux contenues dans le PGCD(a,b)
// PGCD( a=2^n.a' , b=2^n.b' )=2^n.PGCD(a',b')
pow2 = 1u;
while(!(a&1)) // tant que a est pair
{
if(!(b&1)) // si b est de plus pair
{
// PGCD( a=2.a' , b=2.b' )=2.PGCD(a',b')
a >>= 1;
b >>= 1;
pow2 <<= 1;
}
else
{
// on rend <a> pair
do a>>=1;while(!(a&1));
break; // toutes les puissances de 2 du PGCD(a,b) ont ete traitees
}
}
// on rend <b> pair
while(!(b&1)) b>>=1;
// ici les deux nombres sont pairs, le temps de calcul precedent est negligeable
// devant ce qui suit...
// information : la difference de deux nombres impairs est pair
do
{
if(a==b)
{
break; // bingo ! PGCD(a,b)=a
}
else if(a > b)
{
a -= b; // PGCD(a,b)=PGCD(a-b,b)
do a>>=1;while(!(a&1)); // on peut rendre <a> pair car on a plus de puissance de deux dans le PGCD
}
else // b > a
{
b -= a; // PGCD(a,b)=PGCD(a,b-a)
do b>>=1;while(!(b&1)); // on peut rendre <b> pair car on a plus de puissance de deux dans le PGCD
}
}while(1);
return pow2*a;
} // pgcdFast()
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.