begin process at 2012 02 05 04:12:41
  Trouver un code source :
 
dans
 
Accueil > 

Code

 > 

Maths & Algorithmes

 > CACUL (RAPIDE) DE PGCD

CACUL (RAPIDE) DE PGCD


 Information sur la source

Note :
10 / 10 - par 2 personnes
10,00 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
Catégorie :Maths & Algorithmes Classé sous :pgcd, rapide, soustraction, modulo, 64 bits Niveau :Débutant Date de création :02/11/2007 Vu / téléchargé :9 716 / 211

Auteur : JCDjcd

Ecrire un message privé
Ce membre participe au partage de revenus publicitaires
Commentaire sur cette source (5)
Ajouter un commentaire et/ou une note


 Description

Cliquez pour voir la capture en taille normale
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

  • //==========================================================================
  • // 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()
//==========================================================================
//                                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()



 Fichier Zip

Les Membres Club peuvent télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !
  • main.cTélécharger ce fichier [Réservé aux membres club]Voir ce fichier4 402 octets
  • pgcd.dswTélécharger ce fichier [Réservé aux membres club]Voir ce fichier531 octets
  • pgcd.exe_Télécharger ce fichier [Réservé aux membres club]45 056 octets
  • res.xlsTélécharger ce fichier [Réservé aux membres club]27 136 octets

Télécharger le zip


 Sources du même auteur

Source avec Zip Source avec une capture COLORATION SYNTAXIQUE
Source avec Zip Source avec une capture ORBITES DES SATELLITES GPS
Source avec Zip Source avec une capture DESSIN D'ARBRES
Source avec Zip Source avec une capture PROGRAMMATION LINEAIRE
Source avec Zip EXTENSION DE CORPS (MATH)

 Sources de la même categorie

Source avec Zip UN EXAMPLE D'APPLICATION EN CUDA DE L'ALGORITHME DE SCAN POU... par oguzaras
Source avec Zip Source avec une capture CHIFFREMENT DE VIGENERE par lajouad
Source avec Zip Source avec une capture ANALYSE SYNTAXIQUE par lajouad
Source avec Zip Source avec une capture STRUCTURE D'UNE MATRICE PAR LES LISTE LINÉAIRE (NON CONTUGUS... par benzarabel
Source avec Zip Source avec une capture DESSINER UNE ARBRE BINAIRE( MODE CONSOLE): par benzarabel

 Sources en rapport avec celle ci

Source avec Zip Source avec une capture TROUVER LES NOMBRES PREMIERS INFÉRIEURS À UNE LIMITE DONNÉE par angrevol
Source avec Zip Source avec une capture CLASS MATRICE C++ par elkasimi2007
PROGRAMME QUI CALCUL LE PPCM ET LE PGCD par AnoSantino
Source avec Zip EASYLIB WIN32 C++ POUR DU PROTOTYPAGE RAPIDE par gourky
Source avec Zip LE QUICKSORT NON-RECURSIF ET L'IMPACT DE L'INSERTIONSORT SUR... par nickydaquick

Commentaires et avis

Commentaire de max12 le 03/11/2007 06:28:27 administrateur CS 10/10

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+

Commentaire de alechevallier le 05/11/2007 12:00:53 10/10

Bonjour, interresant et surtout super impressionnant.
Bravo !

Commentaire de subway le 08/12/2007 17:17:36

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/2
b >>= 1; // b = b/2
}

// Si a est impair
if( !(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
}

Commentaire de JCDjcd le 09/12/2007 17:01:03

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

Commentaire de BruNews le 09/12/2007 18:05:41 administrateur CS

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.

 Ajouter un commentaire


Discussions en rapport avec ce code source dans le forum

Probleme sur un programme qui calcule un pgcd [ par El loco ] Voila j ai un probleme sur le programme suivant, il marche correctement avec une grande serie de nombres mais quand je tape 15 et 32 il me donne un pg Format de données [ par leskritiques ] Voici le programme que je veux modofier :#include "chaine.h"#include "entreeSortie.h"#include "chaine.cpp"#include "entreeSortie.cpp"int pgcd (const i division modulo [ par AngeloVivaldi ] bjr a tous.Voila, je fai en C++ cette operation :c = x % y;vous l'aurez compris c'est une division modulo.Maintenan, sachant ke g y et c, commen trou date et heures en bd [ par systemic_anomaly ] J'ai un prob avec une commande sql depuis deka un certain temps. Il s'agit de la soustraction de 2 heures declarees comme suit : HDepPrev DATE Envoi rapide port série [ par spiritualys ] Hello,J'ai besoin d'aide : je dois envoyer des messages sur un port série avec un temps bien précis (inférieur à 6 ms). Les commandes existantes en C Soustraction de chaines converties en heures... [ par Guidelor ] Bonjour à tous !en fait j'ai 2 chaines : "20:48:12" et "21:11:45" lues à partir d'un fichier texteet j'aurais besoin d'un genie qui arriverait à sous PGCD? [ par bethoring ] Tout d'abord bonsoir, je voulais savoir si dans math.h yavé une fonction pour faire un pgcd ( jai regarder dedans et il me semble pas menfin on sai ja tri rapide(quicksort)+tri par tas(heapsort)+simulation graphique [ par mersniyassine ] mon stage d'ete comporte une simulation graphique du tri par tas et du tri rapide, je trouve une difficulté a gerer le code source,merci bien de me fo Evenement trop rapide [ par larion ] Bonjour,Imaginons que nous avons 2 événements, pour exemple :evenement1: WM_LBUTTONDOWN --&gt; Action1evenement2: WM_LBUTTONUP --&gt; Action2S tri rapide (quicksort) et/ou tri par tas(heapsort) urgent [ par mersniyassine ] je trouve une difficulté a simuler graphiquement en C ces 2 trisya t-il quelqu'un qui peut me fournir un code.c compilable sur Turbo C qui effectue u


Nos sponsors


Sondage...

Comparez les prix

CalendriCode

Février 2012
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
272829    

Consulter la suite du CalendriCode

 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 4,150 sec (3)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales