Fibonacci par les matrices — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 11)

Fibonacci par les matrices

Programmes justes : logique de Hoare et invariants · niveau 2

Énoncé

On reprend $M = (0111)$ et la fonction puissance(long[][] A, int b) du cours.

Montrer par récurrence que, pour $k \geq 1$ , $M^{k} = (f (k - 1) f (k) f (k) f (k + 1))$ .
Dérouler le calcul de $M^{9}$ : valeurs successives de $e$ et nombre de produits de matrices. En déduire $f (10)$ .
Avec des long, jusqu'à quel $n$ le calcul de $f (n)$ est-il exact ? Que se passe-t-il au-delà ?

Pour $k = 1$ : $M^{1} = (0111) = (f (0) f (1) f (1) f (2))$ . Si la formule est vraie pour $k$ , alors $M^{k + 1} = M^{k} \times M = (f (k) f (k + 1) f (k - 1) + f (k) f (k) + f (k + 1)) = (f (k) f (k + 1) f (k + 1) f (k + 2))$ .
$e$ prend les valeurs $9, 8, 4, 2, 1, 0$ : cinq tours, donc cinq produits de matrices ( $P \times X$ quand $e$ est impair, $X \times X$ sinon). On obtient $M^{9} = (21343455)$ , donc $f (10) = 55$ (case en bas à droite, qui vaut $f (10)$ d'après la question 1).
$f (92) = 7540113804746346429$ est le dernier terme inférieur à $2^{63} - 1 \approx 9, 22 \times 1 0^{18}$ . Le calcul de $f (93)$ dépasse la capacité d'un long et Java retourne un nombre négatif, sans signaler d'erreur :


f(10) = 55, f(50) = 12586269025, f(90) = 2880067194370816120, f(92) = 7540113804746346429, f(93) = -6246583658587674878

Au-delà, il faut java.math.BigInteger, ou un calcul modulo $m$ comme à l'exercice 11.7.