Exercice 7 - Itérateurs et nombres de Fibonacci

1. Soit $\left[ \begin{array}{l}F_n \\ F_{n-1}\end{array}\right]$, un vecteur de deux nombres de fibonacci consécutifs. Que donne le produit $\left[ \begin{array}{l l}1 & 1 \\ 1 & 0 \end{array}\right] \left[ \begin{array}{l}F_n \\ F_{n-1}\end{array}\right]$ ?
2. Prouvez par récurrence que $\left[ \begin{array}{l l}1 & 1 \\ 1 & 0 \end{array}\right]^n \left[ \begin{arr... ...\end{array}\right] = \left[ \begin{array}{l}F_{n+1} \\ F_n\end{array}\right]$.
3. On calcule donc le $n$-ème nombre de Fibonacci en mettant préalablement la matrice $\left[ \begin{array}{l l}1 & 1 \\ 1 & 0 \end{array}\right]$ à la puissance $n$. Nous allons utiliser pour ce faire la même règle que pour $fastPuissance$. Ecrivez une fonction $multMat$ prenant en paramètre deux quadruplets $(x_{11}, x_{12}, x_{21}, x_{22})$ et $(y_{11}, y_{12}, y_{21}, y_{22})$ représentant deux matrices $X = \left[ \begin{array}{l l}x_{11} & x_{12} \\ x_{21} & x_{22} \end{array}\right]$ et $Y = \left[ \begin{array}{l l}y_{11} & y_{12} \\ y_{21} & y_{22} \end{array}\right]$. $multMat$ retourne un quadruplet représentant le produit matriciel $XY$.
4. Définir une fonction $matPow(X, n)$ mettant un matrice $X$, à la puissance $n$. Vous utiliserez $\mathcal{I}(\delta, multMat, n, X)$.
5. Ecrire une fonction $multMatVec$ retournant le produit d'une matrice, représentée par un quadruplet, et d'un vecteur, représenté par un couple.
6. Ecrire en C la fonction quadruplet applyFDQ(int (*delta)(int k), unsigned long (*f)(int, quadruplet), int n, quadruplet x), vous utiliserez le même modèle mathématique, mais en transmettant comme deuxième paramètre à $f$ un quadruplet.
7. Ecrire la fonction $fastFibonacci(n)$, retournant le $n$-ième nombre de fibonacci.
8. Quelle est la complexité de $fastFibonacci$ ?
9. Implémenter les fonctions :
   1. quadruplet multMat(quadruplet x, quadruplet y)
   2. quadruplet applyFDQ(unsigned long (*delta)(unsigned long), quadruplet (*f)(unsigned long, quadruplet), unsigned long n, quadruplet x
   3. quadruplet matPow(quadruplet x, unsigned long n)
   4. couple multMatVec(quadruplet x, couple y)
   5. unsigned long fastFibonacciIT(unsigned long l).