Suite de Fibonacci (2)⚓︎
Les premiers termes de la suite de Fibonacci sont :
- 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 :
É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
- on pose
- 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
- on pose
- Si
Exemples
>>> 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)
def fibpy-und2(n):bksl-nl ...bksl-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-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-nl bksl-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 dereturn 1 % m
- pour \(m>1\), on a
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...
>>> f_nm1, f_n = fib_2(10**16, 10**9)
>>> f_n
888671875
Ainsi \(F_{10^{16}} = \cdots 888671875\)
Z