Cacul (rapide) de pgcd

Soyez le premier à donner votre avis sur cette source.

Vue 12 247 fois - Téléchargée 334 fois

Description

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()

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

BruNews
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
17
En plus cout en performance, l'emploi de pow() banirait le portage de l'algo vers les grands entiers.

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.
cs_JCDjcd
Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
2
ouais c'est exactement le meme algorithme

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
cs_subway
Messages postés
1
Date d'inscription
mercredi 8 octobre 2003
Statut
Membre
Dernière intervention
8 décembre 2007

Voici un algorithme similaire pour Unix en utilisant toujours l'algorithme binaire pour calculer le PGCD de deux nombres.

/**
* 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
}
alechevallier
Messages postés
1
Date d'inscription
mardi 4 juillet 2006
Statut
Membre
Dernière intervention
5 novembre 2007

Bonjour, interresant et surtout super impressionnant.
Bravo !
cs_max12
Messages postés
1491
Date d'inscription
dimanche 19 novembre 2000
Statut
Modérateur
Dernière intervention
7 juillet 2014

Cette source sera supprimée ... non pas vrai :P C'est une source innovante par ses explications et son algorithme, comme je disais on est pas bucké. Encore une source instructive, comme 99.9999999% de tes sources. (La perfection existe pas)

A+

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.