Le pire cas d'Euclide — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 11)

Le pire cas d'Euclide

Programmes justes : logique de Hoare et invariants · niveau 3 (difficile)

Énoncé

On reprend la fonction pgcd du cours : tant que $b \neq = 0$ , on remplace $(a, b)$ par $(b, a mod b)$ .

Énoncer l'invariant et le variant de la boucle.
Compter les tours pour $(a, b) = (f (k + 1), f (k))$ , deux termes consécutifs de la suite de Fibonacci.
Montrer que, si $a \geq b > 0$ , deux tours consécutifs divisent $a$ au moins par $2$ . En déduire que le nombre de tours est en $O (lo g a)$ .
Vérifier par programme quel couple $1 \leq b \leq a \leq 1000$ demande le plus de tours.

Corrigé

Invariant : $pgcd (a, b) = pgcd (a_{0}, b_{0})$ (valeurs initiales), car $pgcd (a, b) = pgcd (b, a mod b)$ . Variant : $b$ , entier positif qui décroît strictement puisque $a mod b < b$ .
$f (k + 1) mod f (k) = f (k - 1)$ (car $f (k + 1) = f (k) + f (k - 1)$ et $f (k - 1) < f (k)$ pour $k \geq 3$ ). Le couple $(f (k + 1), f (k))$ devient donc $(f (k), f (k - 1))$ : on descend la suite d'un cran à chaque tour, jusqu'à $(f (3), f (2)) = (2, 1)$ , puis $(1, 0)$ . Il faut $k - 1$ tours :


pgcd(f(6), f(5)) : 4 tours
pgcd(f(11), f(10)) : 9 tours
pgcd(f(21), f(20)) : 19 tours
pgcd(f(41), f(40)) : 39 tours

Après un tour, $(a, b)$ devient $(b, r)$ avec $r = a mod b$ , puis après un second tour la première composante vaut $r$ . Si $b \leq a /2$ , alors $r < b \leq a /2$ ; si $b > a /2$ , alors $r = a - b < a /2$ . Dans les deux cas, deux tours divisent $a$ au moins par $2$ : au plus $2 lo g_{2} a + 2$ tours, $O (lo g a)$ .
Le programme Exercices11.java essaie tous les couples :


pire cas pour 1 <= b <= a <= 1000 : 14 tours, (a, b) = (987, 610)

Ce sont deux termes consécutifs de Fibonacci, $f (16)$ et $f (15)$ : c'est le théorème de Lamé (1844), les couples de Fibonacci sont les pires cas de l'algorithme d'Euclide.