Probleme – Élever à une puissance, et Fibonacci en $\Theta (\log n)$

1. L'exponentiation rapide.

(* Renvoie x^n. Précondition : n >= 0.
   Complexité : Theta(log n) multiplications. *)
let rec puissance x n =
  if n = 0 then 1
  else if n mod 2 = 0 then let y = puissance x (n / 2) in y * y
  else x * puissance x (n - 1)

Terminaison : variant $n$, qui décroît strictement — soit divisé par deux, soit diminué de $1$ ; et deux tours ne peuvent pas être impairs de suite, donc $n$ est au moins divisé par deux tous les deux appels : $\Theta (\log n)$ appels.

Correction : par récurrence forte sur $n$. Si $n$ est pair, $x^n=(x^{n/2}{)}^2$ ; s'il est impair, $x^n=x\cdot x^{n-1}$. Le point à ne pas manquer est le let y = ... in y <em> y : écrire puissance x (n/2) </em> puissance x (n/2) ferait deux appels au lieu d'un, et l'on retomberait sur $T(n)=2T(n/2)+1=\Theta (n)$ — tout le gain perdu par une lettre.

Multiplications comptées :

(Le calcul a été fait modulo $10^9+7$ pour que rien ne déborde ; le comptage ne s'en trouve pas modifié.)

2. La formule matricielle. Posons $M=\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$. Par récurrence sur $n\ge 1$.

Base : $M^1=\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)=\left(\begin{array}{cc}{F}_2& F_1\\ F_1& F_0\end{array}\right)$ avec $F_0=0$, $F_1=F_2=1$.

Hérédité : si $M^n=\left(\begin{array}{cc}{F}_{n+1}& F_n\\ F_n& F_{n-1}\end{array}\right)$, alors

$$M^{n+1}=M\cdot M^n=\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)\left(\begin{array}{cc}{F}_{n+1}& F_n\\ F_n& F_{n-1}\end{array}\right)=\left(\begin{array}{cc}{F}_{n+1}+F_n& F_n+F_{n-1}\\ F_{n+1}& F_n\end{array}\right)=\left(\begin{array}{cc}{F}_{n+2}& F_{n+1}\\ F_{n+1}& F_n\end{array}\right).$$

La récurrence de Fibonacci est exactement ce qui fait fonctionner le produit.

3. Le calcul et la comparaison. On applique l'exponentiation rapide au produit de matrices $2\times 2$, qui est associatif : $F_n$ est le coefficient en haut à droite de $M^n$.

type mat = { a : int; b : int; c : int; d : int }
let produit m n =
  { a = m.a*n.a + m.b*n.c; b = m.a*n.b + m.b*n.d;
    c = m.c*n.a + m.d*n.c; d = m.c*n.b + m.d*n.d }

(* F(n) en Theta(log n) produits de matrices 2x2. Précondition : n >= 0. *)
let rec puiss_mat m n =
  if n = 0 then { a = 1; b = 0; c = 0; d = 1 }
  else if n mod 2 = 0 then let p = puiss_mat m (n / 2) in produit p p
  else produit m (puiss_mat m (n - 1))

let fibonacci n =
  if n = 0 then 0 else (puiss_mat { a = 1; b = 1; c = 1; d = 0 } n).b

Les trois méthodes ont été confrontées et donnent les mêmes valeurs partout où les trois sont calculables.

Ce que ce tableau met en scène — et il y a trois régimes, pas deux.

Le récursif naïf est exponentiel : $\Theta ({\phi }^n)$ appels, parce qu'il recalcule les mêmes valeurs. C'est le défaut du chapitre chap:dynamique, et la mémoïsation le ramène à $\Theta (n)$.

L'itératif est en $\Theta (n)$ additions, et c'est déjà excellent. Diviser pour régner n'a rien à voir avec la correction de la récursion naïve : les deux améliorations sont indépendantes.

Le matriciel est en $\Theta (\log n)$ produits. Il n'y a plus rien à mémoïser — il n'y a plus de sous-problème répété. Le gain vient d'ailleurs : d'avoir remarqué que la récurrence est linéaire, donc représentable par une matrice, donc justiciable de l'exponentiation rapide. Le même procédé accélère toute récurrence linéaire à coefficients constants.

Une nuance sur le « $\Theta (\log n)$ ». $F_{90}$ tient encore dans un entier de $63$ bits ; $F_{200}$ non. En arithmétique exacte, les nombres manipulés ont $\Theta (n)$ chiffres, et chaque produit coûte alors $\Theta (n^{1,585})$ par Karatsuba. La complexité en opérations est logarithmique ; la complexité en temps ne l'est pas. Compter les opérations suppose qu'elles sont à coût constant, et il faut le dire.