Accueil🇫🇷Chercher

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

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(log2 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(n2).

Notes et références

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, et Clifford Stein, Introduction Ă  l'algorithmique, 1176 p., Section 31.2
  2. J Stein, « Computational problems associated with Racah algebra », Journal of Computational Physics, vol. 1, no 3,‎ , p. 397–405 (ISSN 0021-9991, DOI 10.1016/0021-9991(67)90047-2, lire en ligne, consulté le )
  3. Donald E. Knuth, The Art of Computer Programming, vol. II : Seminumerical Algorithms, Addison-Wesley,

Voir aussi

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.