Algorithme binaire de calcul du PGCD
# 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. 902 dans). L'algorithme a été publié par Josef Stein en 1967, bien qu'il semble avoir été connu en Chine dès le Ier siècle.

## Principe

L'algorithme applique itérativement les règles suivantes pour calculer le PGCD de deux nombres a et b (on suppose a supérieur à b) :

| Si | alors |
| - | - |
| a = 0 | pgcd(0, b) = b |
| a et b sont pairs | pgcd(a, b) = 2 × pgcd(a/2, b/2) |
| a est impair, b pair | pgcd(a, b) = pgcd(a, b/2) |
| a est pair, b impair | pgcd(a, b) = pgcd(a/2, b) |
| a et b impairs | pgcd(a, b) = pgcd( (a - b)/2, b) |

## Exemple

pgcd(30, 24) = 2 × pgcd(15, 12) = 2 × pgcd(15, 6) = 2 × pgcd(15, 3) = 2 × pgcd( (15-3)/2, 3) = 2 × pgcd(6, 3) = 2 × pgcd(3, 3) = 2 × pgcd(0, 3) = 2 × 3 = 6

## Complexité

Si on considère les opérations arithmétiques (soustraction et division par deux) comme unitaires, la complexité est en O(log a), c'est-à-dire en le nombre de chiffres du grand nombre (on suppose a > b). Si ces opérations sont considérées comme linéaires en ce même nombre de chiffres, l'algorithme est en $O(log^2$ a).

En prenant comme taille des entrées le nombre de chiffres n du plus grand nombre, ces complexités deviennent respectivement O(n) et $O(n^2).$

