Algorithme binaire de calcul du PGCD

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^[1]). L'algorithme a été publié par Josef Stein en 1967^[2], bien qu'il semble avoir été connu en Chine dès le I^er siècle^[3].

L'algorithme calcule le PGCD de deux nombres entiers naturels ${\displaystyle a}$ et ${\displaystyle b}$ en appliquant itérativement les identités suivantes :

1. ${\displaystyle pgcd(0,b)=b}$: tous les entiers naturels divisent zéro et ${\displaystyle b}$ est le plus grand entier naturel qui divise ${\displaystyle b}$.
2. ${\displaystyle pgcd(2a,2b)=2\times pgcd(a,b)}$: ${\displaystyle 2}$ est un diviseur commun.
3. ${\displaystyle pgcd(a,2b)=pgcd(a,b)}$ si ${\displaystyle a}$ est impair, ${\displaystyle 2}$ n'est pas un diviseur commun.
4. ${\displaystyle pgcd(a,b)=pgcd(a-b,b)}$si ${\displaystyle a,b}$ sont impairs et ${\displaystyle a\geqslant b}$.

Puisque le PGCD est commutatif (${\displaystyle pgcd(a,b)=pgcd(b,a)}$), ces identités sont vérifiées en inversant les opérandes : ${\displaystyle pgcd(0,b)=b}$, ${\displaystyle pgcd(2a,b)=pgcd(a,b)}$si b impair, etc.

Ainsi on récapitule dans un tableau les différents cas possibles en supposant à chaque étape que ${\displaystyle a\geqslant b}$.

On souhaite calculer le PGCD de ${\displaystyle 30}$ et de ${\displaystyle 24}$.

• ${\displaystyle 30}$ et ${\displaystyle 24}$ sont pairs, ainsi nous sommes le cas 2 : ${\displaystyle pgcd(30,24)=2\times pgcd(15,12)}$;
• ${\displaystyle 15}$ est impair et ${\displaystyle 12}$ est pair, ainsi nous appliquons le cas 3 : ${\displaystyle pgcd(15,12)=pgcd(15,6)}$;
• ${\displaystyle 15}$ est impair et ${\displaystyle 6}$ est pair, ainsi nous appliquons le cas 3 : ${\displaystyle pgcd(15,6)=pgcd(15,3)}$;
• ${\displaystyle 15}$ et ${\displaystyle 3}$ sont impairs , ainsi nous appliquons le cas 4 : ${\displaystyle pgcd(15,3)=pgcd((15-3),3)=pgcd(12,3)}$;
• ${\displaystyle 12}$ est pair et ${\displaystyle 3}$ est impair, ainsi nous appliquons le cas 3 (symétrique) : ${\displaystyle pgcd(12,3)=pgcd(6,3)}$;
• ${\displaystyle 6}$ est pair et ${\displaystyle 3}$ est impair, ainsi nous appliquons le cas 3 (symétrique) : ${\displaystyle pgcd(6,3)=pgcd(3,3)}$;
• ${\displaystyle 3}$ et ${\displaystyle 3}$ sont impairs , ainsi nous appliquons le cas 4 : ${\displaystyle pgcd(3,3)=pgcd((3-3),3)=pgcd(0,3)}$;
• Nous avons finalement le cas 1 : ${\displaystyle pgcd(0,3)=3}$.

Ainsi en remontant les étapes nous trouvons :

${\displaystyle {\begin{aligned}pgcd(30,24)&=2\times pgcd(15,12)\\&=2\times pgcd(15,6)\\&=2\times pgcd(15,3)\\&=2\times pgcd(12,3)\\&=2\times pgcd(6,3)\\&=2\times pgcd(3,3)\\&=2\times pgcd(0,3)\\&=2\times 3=6\\\end{aligned}}}$

Asymptotiquement, l'algorithme a besoin de ${\displaystyle O(n)}$ étapes où ${\displaystyle n}$ 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 ${\displaystyle 2}$. 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ération machine est d'ordre ${\displaystyle n}$, c'est-à-dire ${\displaystyle \log _{2}(\max(a,b))}$.

• Plus grand commun diviseur
• Algorithme d'Euclide

• Portail de l’informatique
• Portail des mathématiques