title: Algorithme binaire de calcul du PGCD
text: # 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).$
  
  