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
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, et Clifford Stein, Introduction Ă l'algorithmique, 1176 p., Section 31.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 )
- Donald E. Knuth, The Art of Computer Programming, vol. II : Seminumerical Algorithms, Addison-Wesley,