Algorithme du pgcd
On a déjà vu une version de l'algorithme du pgcd. Rappelons -là :
algorithme pgcd(a: entier, b: entier) → entier: # a, b ≥ 0
tant que min(a, b) > 0:
a' ← max(a, b) - min(a, b)
b' ← min(a, b)
a, b ← a', b'
rendre max(a, b)La version couramment utilisée est celle utilisant un modulo (opérateur % en algorithmie) qui converge plus vite.
Cet algorithme est basé sur le fait que si la division euclidienne de $a$ par $b$ vaut $a = qb + r$ (avec $q$ et $r$ entiers et $r < b$) on a pgcd(a, b) = pgcd(b, r).
Donnez un algorithme récursif calculant le pgcd en utilisant le modulo.
Knuth analyse en détails cet algorithme dans le tome 2 (partie 3.5.2) de the art of computer programming. Comme à chaque fois avec Knuth : les résultats sont précis, intéressants et très bien écrits. Je ne peux que vous conseiller d'allez y jeter un coup d'œil nous ne ferons en effet ici qu'effleurer le sujet.
Complexité
Avant de prouver sa complexité, commencez par :
Démontrez que si $a\geq b$ alors $a \bmod b < \frac{a}{2}$.
Ceci vous permettra de :
Déduire que le nombre de récursions de l'algorithme récursif utilisant le pgcd est inférieur à $\log_2(\max(a, b))$.
Si l'opération calculant le modulo est élémentaire, en déduire que la complexité de l'algorithme récursif utilisant le pgcd est en $\mathcal{O}(\ln(\max(a, b)))$.
Pgcd et Fibonacci
On va maintenant montrer que cette complexité est atteinte. Pour cela, exhibons d'étranges propriétés des éléments de la suite de Fibonacci.
Si $F(n)$ est le $n$ème nombre de la suite de Fibonacci, montrez que $F(n) \bmod F(n-1) = F(n-2)$.
En déduire que :
Il y a exactement $n$ récursions de l'algorithme récursif utilisant le pgcd pour calculer le pgcd de $F(n+1)$ et $F(n)$.
On a même mieux :
Si pour $a> b$ il y a au moins $n$ récursions de l'algorithme récursif, alors $a\geq F(n+1)$ et $b\geq F(n)$.
Si l'opération calculant le modulo est élémentaire, en conclure que la complexité de l'algorithme récursif utilisant le pgcd est en $\mathcal{O}(\ln(\min(a, b)))$.
Si cela vous intéresse, vous pouvez jeter un petit coup d'œil au lien suivant qui liste quelques propriétés liées au pgcd des nombres de la suite de Fibonacci :
pgcd binaire
Cet algorithme, répertorié dès le 1er siècle (Knuth cite le 九章算术 chapitre 1 section 6) puis publié dans sa forme actuelle en 1967 par Stein.
algorithme pgcd_binaire(a: entier, b: entier) → entier: # a, b ≥ 0
si b == 0:
rendre a
si a et b sont pairs:
rendre 2 * pgcd_binaire(a // 2, b // 2)
si a est impair et b pair:
rendre pgcd_binaire(a, b // 2)
si a est pair et b impair:
rendre pgcd_binaire(a // 2, b)
si a et b sont impairs:
si a < b:
a, b ← b, a
rendre pgcd_binaire(a - b, b)Montrez que l'algorithme pgcd_binaire(a, b) calcule bien le pgcd des deux entiers positifs a et b.
Quelle est la complexité de cet algorithme ?