L'exponentiation matricielle

Peut-on battre le coût linéaire ? Oui, en écrivant la récurrence sous forme matricielle. On empile deux termes consécutifs et on remarque :

   | F(n+1) |   | 1  1 |   | F(n)   |
   |        | = |      | * |        |
   | F(n)   |   | 1  0 |   | F(n-1) |

Multiplier par cette matrice fait avancer d'un cran. L'appliquer n fois donne une identité remarquable :

   | 1  1 |^n   | F(n+1)  F(n)   |
   |      |   = |                |
   | 1  0 |     | F(n)    F(n-1) |

Calculer F(n) revient donc à élever cette matrice à la puissance n. Or une puissance se calcule par exponentiation rapide : au lieu de multiplier n fois, on élève au carré à répétition en lisant n en binaire.

   M^16 = ((((M^2)^2)^2)^2)      (4 elevations au carre, pas 15 produits)

Coût : logarithmique, O(log n) multiplications de matrices 2×2. On atteint F(1 000 000) en une poignée d'opérations, là où l'itération en demanderait un million.

Cette écriture livre en prime de belles identités. En prenant le déterminant de l'égalité ci-dessus (celui de la matrice de base vaut −1, donc celui de sa puissance n vaut (−1)^n) :

   F(n-1) * F(n+1) − F(n)²  =  (−1)^n       (identité de Cassini)

Une seule idée — voir la récurrence comme une matrice — fournit à la fois l'algorithme le plus rapide et des formules élégantes. C'est toute la puissance de l'algèbre linéaire mise au service d'une suite d'entiers.