En informatique, en mathématiques, l'algorithme du PGCD binaire est un algorithme pour calculer le plus grand commun diviseur de deux nombres entiers écrits en binaire (voir Problème 31.1, p. 870-871). L'algorithme a été publié par Josef Stein en 1967, bien qu'il semble avoir été connu en Chine dès le .

Algorithme L'algorithme calcule le PGCD de deux nombres entiers naturels et en appliquant itérativement les identités suivantes :

: tous les entiers naturels divisent zéro et est le plus grand entier naturel qui divise . : est un diviseur commun. si est impair, n'est pas un diviseur commun. si sont impairs et .

Puisque le PGCD est commutatif (), ces identités sont vérifiées en inversant les opérandes : , si b impair, etc.

Ainsi on récapitule dans un tableau les différents cas possibles en supposant à chaque étape que . +Si ...alors ...b = 0pgcd(a, 0) = aa et b sont pairspgcd(a, b) = 2 × pgcd(a/2, b/2)a est impair, b pairpgcd(a, b) = pgcd(a, b/2)a est pair, b impairpgcd(a, b) = pgcd(a/2, b)a et b impairspgcd(a, b) = pgcd( (a - b), b)

Exemple On souhaite calculer le PGCD de et de .

et sont pairs, ainsi nous sommes le cas 2 : ; est impair et est pair, ainsi nous appliquons le cas 3 : ; est impair et est pair, ainsi nous appliquons le cas 3 : ; et sont impairs , ainsi nous appliquons le cas 4 : ; est pair et est impair, ainsi nous appliquons le cas 3 (symétrique) : ; est pair et est impair, ainsi nous appliquons le cas 3 (symétrique) : ; et sont impairs , ainsi nous appliquons le cas 4 : ; Nous avons finalement le cas 1 : .

Ainsi en remontant les étapes nous trouvons :

Complexité Asymptotiquement, l'algorithme a besoin de étapes où est le nombre de bits dans le plus grand des deux nombres comme toutes les deux étapes réduit au moins l'une des opérandes d'un facteur . Chaque pas fait intervenir peu d'opérations arithmétiques (soustraction et division par deux); lorsque l'on travaille avec des nombres de taille de mots, chaque opération arithmétique se traduit par une seule opération machine, donc le nombre d'opérations machine est d'ordre , c'est-à-dire .

Notes et références

Voir aussi

Plus grand commun diviseur Algorithme d'Euclide

Catégorie:Algorithmique Catégorie:Divisibilité et factorisation