CALCUL DU PGCD DE 2 NBRES PAR SOUSTRACTION (AVEC LES CALCULES INTERMÉDIAIRES)

Commentaire de sibi12 le 02/01/2004 00:26:47

Salut,


je ne connaissais pas cette algo pour les pgcd il a l'air de tendre vite vers le nombre chercher...

Seulement niveau performance ton code est pas top...

si j'ai bien compris tu dois chercher remplacer le plus grand par le reste de la division et jusqu'à ce que ce reste soit nul...l'opérateur modulo est "%"

Je trouvais cette algo tres interressant et je me suis permis de l'accélérrer de facon assez significative... le voici, il y a 3 méthode, celle presente plus haut, la mienne en c++ et la meme en ASM...les mesure sont avec :

#include <windows.h>
#include <iostream> // pour utiliser les entrées et sorties cout et cin
using namespace std;

int PGCDXbY(int pp, int pg)
{
int res=1;
while (res)
{
res = pg % pp;
pg = pp;
pp = res;
};
return pg;
}
int PGCDXbYasm(int pp, int pg)
{
__asm{
mov eax, pg;
mov ebx, pp;
boucle:
xor edx,edx;
div ebx;
mov eax, ebx;
mov ebx, edx;
test edx, edx;
jne boucle;
mov pg, eax;
mov pp, ebx;
}
return pg;
}
int PGCD(int pp, int pg)
{
int res=1;
while(true)     // boncle infinie (j'aurais pu faire avec un for
// ou un while "fini" )
{
res = pg-pp; // On calcule (plus grand nbr) - (le plus petit)        
if (res) // si pp est différent de pg, on indique
{            // le résultat du clacul
if(res>pp) pg=res; // on change les variables celon
else if(res<pp) pg=pp, pp=res; //le plus grand nombre
else    pp=res, pg=pp;           // de res et de pp.
}   //Puis on les replace ds pg et pp et on recommence
else                        
break; //On casse la boucle si pp==pg
}
  return pg;
};

int main()          //Début de la fonction principale
{

SetPriorityClass(GetCurrentProcess(), REALTIME_PRIORITY_CLASS);
SetThreadPriority(GetCurrentThread(),THREAD_PRIORITY_TIME_CRITICAL);
  unsigned int a, b, pg, pp, res, cycle, tps; //Définition des variables
  cout << "Ce Programme calcule"  //Message d'explication
  << " le PGCD de deux nombres . \n"
  << "Entrez deux nombres a et b :\n "
  <<"Entrez a : " << endl;
  cin >> a;               // Entrée du 1er nombre
  cout << "Entrez b : " << endl;
  cin >> b;               //Entrée du seconde nombre
  cout << " " << endl;
  
  if (a<b) pp=a, pg=b;        // On regarde quel est le plus gd
  else if (b<a) pp=b, pg=a;   //nombre des 2 et on les places ds
  else                        //deux variable pp et pg
  { pg=a, pp=b;           //(pp= plus petit et pg= plus grand
    
    cout << "\nCes deux nombres sont egaux donc " // Si les 2 nbres
  << "leurs PGCD est ce meme nombre ." << endl; // sont déjà egaux,
  }               // on indique que leur PGCD est ce même nombre                                                                                        
                      /*On indique le résultat*/
itération = 100
for (int j=0;j<5;j++)
{
tps=0;
for(int i=0;i<itération;i++)
{
__asm
{
rdtsc;
mov cycle,eax;
}
res=PGCD(pp, pg);
__asm
{
rdtsc;
sub eax,cycle;
add tps,eax;
}
};
tps /= itération;

cout << "Le PGCD          de " << a << " et " << b << " est " << res << " en " << tps << "cycle" << endl;  

tps=0;
for(int i=0;i<itération;i++)
{
__asm
{
rdtsc;
mov cycle,eax;
}
res=PGCDXbYasm(pp, pg);
__asm
{
rdtsc;
sub eax,cycle;
add tps,eax;
}
};
tps /= itération;
  
cout << "Le PGCD(XbY ASM) de " << a << " et " << b << " est " << res << " en " << tps << "cycle" << endl;  

tps=0;
for(int i=0;i<itération;i++)
{
__asm
{
rdtsc;
mov cycle,eax;
}
res=PGCDXbY(pp, pg);
__asm
{
rdtsc;
sub eax,cycle;
add tps,eax;
}
};
tps /= itération;

cout << "Le PGCD(XbY)     de " << a << " et " << b << " est " << res << " en " << tps << "cycle" << endl << endl;  

};
system("pause");
  return 0;
}        
      
Voila J'espere que g pas code de connerie... il fait 5 fois chaque code pour avoir une meilleur idée des perormance à cause de la gestion d threads windows.

@+