Avancer

Section 3.4 Nombres de Fibonacci

Comment utiliser efficacement l'ordinateur pour calculer les nombres de Fibonacci?

Définition 3.4.2.

La suite de Fibonacci est définie par récurrence de la façon suivante :

\begin{equation*} F_1=F_2=1\quad\text{et}\quad F_n=F_{n-1}+F_{n-2}\quad\text{pour tout}\;n\geq 3. \end{equation*}

L'algorithme récursif naïf implémenté à l'exercice 2.3.12 a une complexité exponentielle, c'est pourquoi cela prend déjà un temps terriblement long pour calculer \(F_{100}\) de cette façon.

L'algorithme itératif implémenté à l'exercice 1.4.12 est bien meilleur étant donné que sa complexité s'avère linéaire.

Mais on peut mieux faire : nous allons maintenant calculer \(F_{50}\) à l'aide de deux autres algorithmes qui peuvent être plus avantageux, dépendant du contexte et des buts cherchés.

Algorithme 1 : Formule de Binet.

Comme \((F_n)\) est une suite récurrente linéaire, il est possible d'exprimer son terme général à l'aide d'une formule explicite.

Notons

\begin{equation*} \phi_+:=\frac{1+\sqrt{5}}{2}\quad\text{et}\quad\phi_-:=\frac{1-\sqrt{5}}{2}, \end{equation*}

et observons que

\begin{equation*} \phi_++\phi_-=1,\quad\phi_+-\phi_-=\sqrt{5}\quad\text{et}\quad\phi_+\phi_-=-1. \end{equation*}

Étant donné la définition 3.4.2, il suffit de vérifier que

\begin{equation*} G_n:=\left(\phi_+^n-\phi_-^n\right)/\sqrt{5} \end{equation*}

satisfait

\begin{equation*} G_1=G_2=1\quad\text{et}\quad G_n=G_{n-1}+G_{n-2}\quad\text{pour tout}\;n\geq 3. \end{equation*}

  • On voit tout de suite que

    \begin{equation*} \sqrt{5}\,G_1=\phi_+-\phi_-=\sqrt{5} \end{equation*}

    et que

    \begin{equation*} \sqrt{5}\,G_2=\phi_+^2-\phi_-^2=\left(\phi_+-\phi_-\right)\left(\phi_++\phi_-\right)=\sqrt{5}\cdot 1=\sqrt{5}, \end{equation*}

    d'où \(G_1=G_2=1\text{.}\)

  • Pour la relation de récurrence, on a

    \begin{align*} \sqrt{5}\,G_{n-1}+\sqrt{5}\,G_{n-2}&=\phi_+^{n-1}-\phi_-^{n-1}+\phi_+^{n-2}-\phi_-^{n-2}\\ &=\phi_+^{n-1}\cdot 1-\phi_+^{n-2}\cdot(-1)-\phi_-^{n-1}\cdot 1+\phi_-^{n-2}\cdot(-1)\\ &=\phi_+^{n-1}\cdot\left(\phi_++\phi_-\right)-\phi_+^{n-2}\cdot\left(\phi_+\phi_-\right)\\ &\quad\quad-\phi_-^{n-1}\cdot\left(\phi_++\phi_-\right)+\phi_-^{n-2}\cdot\left(\phi_+\phi_-\right)\\ &=\phi_+^n+\cancel{\phi_+^{n-1}\phi_-}-\cancel{\phi_+^{n-1}\phi_-}\\ &\quad\quad-\bcancel{\phi_-^{n-1}\phi_+}-\phi_-^n+\bcancel{\phi_-^{n-1}\phi_+}\\ &=\sqrt{5}\,G_n, \end{align*}

    d'où \(G_n=G_{n-1}+G_{n-2}\) pour tout \(n\ge 3\text{.}\)

Dans cette formule, seul le premier terme importe vraiment. En effet, comme

\begin{equation*} \left|\frac{1-\sqrt{5}}{2}\right|\approx 0{,}62, \end{equation*}

le terme

\begin{equation*} \frac{(1-\sqrt{5})^n}{2^n\sqrt{5}} \end{equation*}

est assez petit pour que \(F_n\) soit égal à l'entier le plus proche de

\begin{equation*} \frac{(1+\sqrt{5})^n}{2^n\sqrt{5}}. \end{equation*}

Évaluez le code suivant pour calculer \(F_{50}\) à l'aide de la formule de Binet.

On en déduit que \(F_{50}=12\,586\,269\,025\text{.}\)

A priori, il n'y a pas mieux qu'une formule explicite. Pourtant, la nature de celle-ci fait en sorte que des erreurs d'arrondis liées à la présence de \(\sqrt{5}\) la rendent vite inutile pour obtenir la valeur exacte de l'entier \(F_n\text{.}\)

Algorithme 2 : Exponentiation matricielle rapide.

Nous allons maintenant transformer l'évaluation d'un terme de la suite \((F_n)\) en un problème d'exponentiation grâce au calcul matriciel.

Nous allons établir cette formule à l'aide d'une preuve par récurrence.

  • Pour \(n=3\text{,}\) on a

    \begin{equation*} \begin{bmatrix}1&1\\1&0\end{bmatrix}^2=\begin{bmatrix}2&1\\1&1\end{bmatrix}, \end{equation*}

    ce qui coïncide bien avec

    \begin{equation*} \begin{bmatrix}F_3&F_2\\F_2&F_1\end{bmatrix}. \end{equation*}

  • Supposons que pour un certain entier \(n\ge 3\) on ait

    \begin{equation*} \begin{bmatrix}1&1\\1&0\end{bmatrix}^{n-1}=\begin{bmatrix}F_n&F_{n-1}\\F_{n-1}&F_{n-2}\end{bmatrix}. \end{equation*}

    Alors par produit matriciel, on a

    \begin{align*} \begin{bmatrix}1&1\\1&0\end{bmatrix}^n&=\begin{bmatrix}1&1\\1&0\end{bmatrix}^{n-1}\begin{bmatrix}1&1\\1&0\end{bmatrix}\\ &=\begin{bmatrix}F_n&F_{n-1}\\F_{n-1}&F_{n-2}\end{bmatrix}\begin{bmatrix}1&1\\1&0\end{bmatrix}\\ &=\begin{bmatrix}F_n+F_{n-1}&F_n\\F_{n-1}+F_{n-2}&F_{n-1}\end{bmatrix}, \end{align*}

    ce qui coïncide bien avec

    \begin{equation*} \begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix} \end{equation*}

    car, par définition 3.4.2, on a

    \begin{equation*} F_n+F_{n-1}=F_{n+1}\quad\text{et}\quad F_{n-1}+F_{n-2}=F_n. \end{equation*}

    La propriété est donc vraie pour \(n+1\text{,}\) ce qui achève la démonstration.

Évaluez le code suivant pour calculer \(F_{50}\) à l'aide d'une exponentiation matricielle rapide implémentée en Python à l'aide de NumPy.

On en déduit à nouveau que \(F_{50}=12\,586\,269\,025\text{.}\)

Quoique moins rapide que la formule de Binet, cet algorithme a le mérite de donner des valeurs exactes de \(F_n\) pour des valeurs de \(n\) plus nombreuses. Et si on tient compte de la complexité de l'addition utilisée dans l'approche itérative utilisée dans l'exercice 1.4.12, il s'avère plus rapide que cette dernière.

Atttention : Notez toutefois que cette implémentation pose un problème à partir de \(n=92\text{.}\) Pour aller plus loin sans erreur, on peut utiliser Sage, par exemple.