Suite de Fibonacci (2)⚓︎

Les premiers termes de la suite de Fibonacci sont :

\[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \cdots\]

Les deux premiers termes sont \(0\) et \(1\).
À partir du troisième, un terme est la somme des deux précédents.

Il existe une formule récursive efficace pour calculer deux nombres de Fibonacci consécutifs.

On pourra poser \(F_{-1} = 1\) de sorte que \(F_{-1} + F_0 = F_1\).

Pour \(m>0\), on admet que :

\[\begin{cases} F_{2k-1} = F_{k}^{2} + F_{k-1}^{2}\\ F_{2k} = F_{k}^{2} + 2×F_{k}×F_{k-1}\\ F_{2k+1} = F_{2k} + F_{2k-1} \end{cases}\]

Écrire une fonction récursive fib_2 telle que fib_2(n) renvoie le couple \((F_{n-1}, F_n)\)

Méthode appliquée à n = 9

L'appel fib_2(9) souhaite renvoyer \((F_8, F_9)\)
\(9\) est impair, on va demander \((F_7, F_8)\), on pourra en déduire \(F_9\)
On appelle fib_2(8)
\(8\) est pair, on va demander \((F_3, F_4)\)
On appelle fib_2(4)
\(4\) est pair, on va demander \((F_1, F_2)\)
On appelle fib_2(2)
\(2\) est pair, on va demander \((F_0, F_1)\)
On appelle fib_2(1)
\(1\) est un cas de base, fib_2(1) renvoie (0, 1)
On déduit
- \(F_1 = F_1^2 + F_0^2 = 1\)
- \(F_2 = F_1^2 + 2×F_1×F_0 = 1\)
- l'appel fib_2(2) renvoie (1, 1)
On déduit
- \(F_3 = F_2^2 + F_1^2 = 2\)
- \(F_4 = F_2^2 + 2×F_2×F_1 = 3\)
- l'appel fib_2(4) renvoie (2, 3)
On déduit
- \(F_7 = F_4^2 + F_3^2 = 13\)
- \(F_8 = F_4^2 + 2×F_4×F_3 = 21\)
- l'appel fib_2(8) renvoie (13, 21)
On déduit
- \(F_9 = F_8 + F_7 = 34\)
- l'appel fib_2(9) renvoie (21, 34)

Indice : Algorithme

Si n est un cas de base, on renvoie la réponse directement.
Sinon,
- Si n est pair, alors
  - on pose k = n // 2
  - on fait un appel récursif avec k
  - on déduit la réponse pour n
- Sinon, n est impair, et alors
  - on pose k = n - 1
  - on fait un appel récursif avec k, qui est pair, lui
  - on déduit la réponse pour n

Exemples

🐍 Console Python

>>> fib_2(0)
(1, 0)
>>> fib_2(1)
(0, 1)
>>> fib_2(2)
(1, 1)
>>> fib_2(3)
(1, 2)
>>> fib_2(9)
(21, 34)
>>> fib_2(4)
(2, 3)

###

# Testsbksl-nlassert fibpy-und2(0) == (1, 0)bksl-nlassert fibpy-und2(1) == (0, 1)bksl-nlassert fibpy-und2(2) == (1, 1)bksl-nlassert fibpy-und2(3) == (1, 2)bksl-nlassert fibpy-und2(9) == (21, 34)bksl-nlassert fibpy-und2(4) == (2, 3)bksl-nlbksl-nlbksl-nl# Autres testsbksl-nlbksl-nlfibpy-undmemo = [0, 1]bksl-nlfor py-und in range(100):bksl-nl fibpy-undmemo.append(fibpy-undmemo[-1] + fibpy-undmemo[-2])bksl-nlbksl-nlfor n in range(1, 100):bksl-nl fpy-undn, fpy-undnm1 = (fibpy-undmemo[n - 1], fibpy-undmemo[n])bksl-nl assert fibpy-und2(n) == (fpy-undn, fpy-undnm1), f"Erreur avec {n=}"bksl-nlbksl-nlbksl-nldef secret799py-undfibpy-und2(n):bksl-nl """Renvoie (Fpy-und{n - 1}, Fpy-und{n})bksl-nl deux nombres de Fibonacci consécutifsbksl-nl on utilise les variables fpy-undnm1 et fpy-undnbksl-nl """bksl-nl # cas de basebksl-nl if n == 0:bksl-nl fpy-undnm1 = 1bksl-nl fpy-undn = 0bksl-nl elif n == 1:bksl-nl fpy-undnm1 = 0bksl-nl fpy-undn = 1bksl-nlbksl-nl # cas généralbksl-nl elif n % 2 == 0:bksl-nl # n est pairbksl-nl k = n // 2bksl-nl fpy-undkm1, fpy-undk = secret799py-undfibpy-und2(k)bksl-nl fpy-undnm1 = fpy-undk py-str fpy-undk + fpy-undkm1 py-str fpy-undkm1bksl-nl fpy-undn = fpy-undk py-str (fpy-undk + 2 py-str fpy-undkm1)bksl-nl else:bksl-nl # n est impairbksl-nl k = n - 1bksl-nl fpy-undkm1, fpy-undk = fibpy-und2(k)bksl-nl fpy-undnm1 = fpy-undkbksl-nl fpy-undn = fpy-undkm1 + fpy-undkbksl-nlbksl-nl return fpy-undnm1, fpy-undnbksl-nlbksl-nlbksl-nl# gros testsbksl-nlfor e in range(2, 7):bksl-nl n = 10py-strpy-strebksl-nl attendu = secret799py-undfibpy-und2(n)bksl-nl assert fibpy-und2(n) == attendu, f"Erreur avec {n=}"bksl-nlbksl-nl ∞/∞

def fibpy-und2(n):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert fibpy-und2(0) == (1, 0)bksl-nlassert fibpy-und2(1) == (0, 1)bksl-nlassert fibpy-und2(2) == (1, 1)bksl-nlassert fibpy-und2(3) == (1, 2)bksl-nlassert fibpy-und2(9) == (21, 34)bksl-nlassert fibpy-und2(4) == (2, 3)bksl-nlbksl-nldef fibpy-und2(n):bksl-nl """Renvoie (Fpy-und{n - 1}, Fpy-und{n})bksl-nl deux nombres de Fibonacci consécutifsbksl-nl on utilise les variables fpy-undnm1 et fpy-undnbksl-nl """bksl-nl # cas de basebksl-nl if n == 0:bksl-nl fpy-undnm1 = 1bksl-nl fpy-undn = 0bksl-nl elif n == 1:bksl-nl fpy-undnm1 = 0bksl-nl fpy-undn = 1bksl-nlbksl-nl # cas généralbksl-nl elif n % 2 == 0:bksl-nl # n est pairbksl-nl k = n // 2bksl-nl fpy-undkm1, fpy-undk = fibpy-und2(k)bksl-nl fpy-undnm1 = fpy-undk py-str fpy-undk + fpy-undkm1 py-str fpy-undkm1bksl-nl fpy-undn = fpy-undk py-str (fpy-undk + 2 py-str fpy-undkm1)bksl-nl else:bksl-nl # n est impairbksl-nl k = n - 1bksl-nl fpy-undkm1, fpy-undk = fibpy-und2(k)bksl-nl fpy-undnm1 = fpy-undkbksl-nl fpy-undn = fpy-undkm1 + fpy-undkbksl-nlbksl-nl return fpy-undnm1, fpy-undnbksl-nlbksl-nl

A

Si on regarde les opérations couteuses, il s'agit uniquement des multiplications entre deux grands nombres. Il y en a trois à chaque fois qu'on fait un appel récursif avec une entrée paire.

On rappelle que le nombre de fois où on peut diviser un entier par deux est environ son logarithme en base 2.

Le cout de fib_2(n) est donc environ \(3\log(n)\) multiplications entre grands entiers. C'est nettement plus efficace qu'une méthode itérative classique qui fait \(n\) additions entre grands entiers.

Calcul modulaire⚓︎

Paragraphe pour les élèves en maths expertes ou en prépa, ou pour les enseignants

Souvent, on s'intéresse au résultat d'une opération modulo \(m\) où \(m\) est un entier qui tient dans un demi-mot machine (\(m\) est aussi parfois un nombre premier). De sorte qu'un produit tient encore dans un conteneur de la taille d'un mot machine. On peut alors faire une réduction modulo \(m\) et travailler uniquement modulo \(m\).

Attention, ceci n'est valable que pour les opérations d'addition, soustraction et multiplication. Pour les divisions, c'est bien plus technique...

Voici alors une version de fib_2 qui prend un paramètre supplémentaire \(m\) le modulo du résultat attendu.

Deux points techniques

Les plus avertis noteront deux choses :

il faut que \(m\) soit légèrement plus petit que la moitié d'un mot machine. Plus précisément, ici, il faut que \(3m^2\) tienne dans un mot machine.
\(m\) est un entier non nul et
- pour \(m>1\), on a m % 1 qui est égal à 1
- mais dans le rare cas où \(m=1\), on a m % 1 égal à 0
- cet oubli est une source d'erreur délicate
- Il ne faut donc pas écrire return 1 au lieu de return 1 % m

🐍 Script Python

def fib_2(n, m):
    """Renvoie (F_{n-1}, F_{n}) chacun modulo m
        deux nombres de Fibonacci consécutifs
    on utilise les variables f_nm1 et f_n
    """
    # cas de base
    if n == 0:
        f_nm1 = 1
        f_n = 0
    elif n == 1:
        f_nm1 = 0
        f_n = 1

    # cas général
    elif n % 2 == 0:
        # n est pair
        k = n // 2
        f_km1, f_k = fib_2(k, m)
        f_nm1 = f_k * f_k  +  f_km1 * f_km1
        f_n = f_k * f_k  +  2 * f_km1
    else:
        # n est impair
        k = n - 1
        f_km1, f_k = fib_2(k, m)
        f_nm1 = f_k
        f_n = (f_km1 + f_k) % m

    return f_nm1 % m, f_n % m

Un tel code permet de calculer facilement les 9 derniers chiffres de \(F_{10^{16}}\) alors qu'avec une méthode itérative classique, il faudrait plusieurs milliards d'années de calcul...

🐍 Console Python

>>> f_nm1, f_n = fib_2(10**16, 10**9)
>>> f_n
888671875

Ainsi \(F_{10^{16}} = \cdots 888671875\)

Z