Python suite de Fibonacci

Bonjour,

Je suis en train d’essayer d’implémenter une fonction qui me permette de calculer la nième valeur de la suite de Fibonacci. J’ai d’abord essayé d’utiliser la récursivité, mais cette méthode n’est pas assez efficace. En fouillant un peu, j’ai vu que l’on pouvait utiliser le nombre d’or comme coefficient multiplicateur. Le problème que j’ai trouvé avec cette technique, c’est que le coefficient n’est pas tout-à-fait égal à φ, surtout au début de la suite, et que donc la solution φ^n^ ne fonctionnait pas bien au delà d’un plafond assez bas.

J’ai donc essayé quelque chose de la forme u~n~ = u~N~ * φ^(n-N)^, ce qui marche plutôt bien… Tant que n <= 78. A partir de là, le programme bloque à N = 77 et je ne comprends pas vraiment pourquoi.

Pourriez-vous m’aider ?

@flopy78

N’hésite pas à poster ton code pour qu’on puisse t’aider, parce que j’avoue que j’ai du mal à comprendre ta formule, est-ce $u_n = u_N \times \phi^{n-N}$ ? Comment est ce que tu choisi $N$ ?

Au dela de ça, tu peux également utiliser la programmation dynamique pour obtenir une performance linéaire, ou alors utiliser l’expression fonctionnelle exacte

Il existe une formule à base du nombre d’or, qui donne les valeurs précises ; elle est donnée sur la page wikipédia : https://fr.wikipedia.org/wiki/Suite_de_Fibonacci#Expression_fonctionnelle Elle fonctionne pour n’importe quelle valeur de n, petite ou grande.

La formule que tu donnes est assez incompréhensible, avec des n minuscules et majuscules ; je ne vois pas pourquoi tu as 2 symboles différents.

Dans la bonne formule, on fait la différence entre 2 nombres, et pour N=78, peut-être que le plus grand des 2 nombres dépasse les limites autorisées.

A vérifier avec ton programme, comment as-tu déclaré tes variables intermédiaires, quels sont les plus grands nombres que tu peux traiter avec tel ou tel type de données.

Bonjour,

Excusez-moi, j’ai oublié de joindre mon code :

from numpy import sqrt

phi = (1 + sqrt(5)) / 2

def _fibo(n,N,u_N):
    return round(u_N * phi**(n-N))

def fibo(n):
    N = 10
    u_N = 55
    n_max = 2



    while n_max < n:
        i = 0
        while _fibo(n_max,N,u_N) == _fibo(n_max - 1,N,u_N) + _fibo(n_max - 2,N,u_N):
            n_max += 1
            i += 1

        n_max -= 1

        u_N = _fibo(n_max,N,u_N)
        N = n_max
        
        print(N,u_N,n_max)
    

    return _fibo(n,N,u_N)

L’objectif de mon algorithme est justement de choisir le plus petit N possible qui ne donne pas un résultat faux pour N (si on prend un N trop petit et un n trop grand, le résultat est faux à cause de l’approximation qui est faite en disant que $fibo(n + 1) = φ * fibo(n)$.

Au début il marche très bien, mais pour une raison qui m’échappe, il bloque, comme je l’ai décrit ci-dessus…

Peut-être que ma solution est encore une autre impasse et qu’il faudra que je me tourne vers d’autres solutions, comme celles que vous me suggérez…

Bonne journée,

@flopy78

Bonjour,

Utiliser une liste reviendrait à utiliser une implémentation itérative, non ? L’implémentation itérative n’est à mon avis pas plus efficace, si ce n’est moins, que la version récursive…

Bonne journée,

@flopy78

Bonjour,

Effectivement, et à ma plus grande surprise, la méthode itérative est extrêmement efficace !!! Par contre, la liste doit prendre une sacré place dans la mémoire pour un N très grand… On pourrait utiliser des variables et ne sauvegarder que N-1 et N-2 :

def fibo_iter(n):
    n_1 = 1 #N - 1
    n_2 = 0 #N - 2

    for i in range(1,n):
        new_n = n_1 + n_2
        n_2 = n_1
        n_1 = new_n
    return n_1

Dans IDLE, c’est très efficace jusqu’à 20578 (au delà de ça, le nombre est trop grand pour pouvoir être converti en chaine de caractère et ne peut pas être affiché par IDLE… ).

Je suis franchement bluffé par l’efficacité de la méthode itérative…

Par ailleurs, en appliquant la formule de wikipedia en Python ainsi (fibo_fonctionnel = lambda n : 1/sqrt(5) * (phi**n - (-1/phi)**n), avec phi = (1+sqrt(5))/2, j’ai obtenu des résultats pas très cohérents avec les autres fonctions, comme fibo_fonctionnel(78) = 8944394323791488.0, alors que fibo_iter(78) = 8944394323791464 (le second résultat ayant été confirmé par ma méthode un peu bancale avec phi et le site dCode).

Je pense que je dois avoir fait une erreur quelque part à ce niveau-là…

Bonne journée,

@flopy78

Il s’agit là d’un problème de précision des flottants (comme précisé ici) et non de calcul. Teste avec un type plus précis (decimal.Decimal par exemple) et tu verras que tu tombes bien sur le bon résultat.

Merci beaucoup !

@PierrotLeFou,

Merci d’éviter de donner des réponses toutes faites. Le but est d'aider le membre à s’améliorer en le mettant sur la piste et en essayant de l’aider à trouver la solution par lui-même. Pas de la donner sur un plateau d’argent.

Arius.

C’est à moitié hors sujet, mais dans du code réel on a tendance à fuir les méthodes récursives et à ne les utiliser que là où c’est strictement indispensable (processus récursifs, cas ou l’on peut prouver que la méthode récursive a une bien meilleure performance). Surtout pour deux raisons : la première (et suffisante à elle seule), c’est que les méthodes récursives sont très souvent difficiles à comprendre, tester et déboguer ; la seconde c’est que selon les conditions d’utilisation, elles peuvent facilement produire des débordements de pile ou autres joyeuseté du genre qu’on ne veut surtout pas avoir en production.

Je ne crois pas être hors sujet non plus.

Dans le cas de la suite de Fibonacci, trouver la fonction récursive n’est pas difficile. Même l’auteur l’a trouvée.

C’est plutôt le temps d’exécution dû au nombre total d’appels et la grandeur de la pile qui pose problème.

Pour ce qui est de la grandeur de la pile, elle sera de l’ordre de n. En effet, dans le pire des cas, on aura un appel pour:

n, n-1, n-2, ..., 1, 0

soit n+1 appels.

Le nombre total d’appels est nettement moins que prévu. Il n’est pas de l’ordre de 2**n. Il devient tout de même rapidement très grand. On peut le voir comme un arbre binaire pour lequel la profondeur d’une branche est toujours un de moins que celle de l’autre branche.

Le code suivant montre comment le calculer avec vérification.

def fibo(n):
    global c
    c += 1   # Compter le nombre d'appels.
    if n <= 0: return 0
    if n == 1: return 1
    return fibo(n-1) + fibo(n-2)
# Calcul du nombre d'appels.
F = [1, 1]   # 1 appel pour 0 et 1
for n in range(2, 100+1):   # Jusqu'à 100 ...
    F.append(F[-1] + F[-2] + 1)
# Vérification (jusqu'à 30, sinon c'est trop long ...).
for n in range(30+1):
    c = 0   # Nombre d'appel pour une valeur de n
    fibo(n)   # Je me fiche du résultat.
    if c != F[n]: print(f"erreur pour {n}, c={c}, F={F[n]}")
print(F[78])

Ce qui donne:

28944668049352441                                                                                                       

L’évaluation est bonne jusqu’à au moins 30. On voit pourquoi c’est si long pour le terme 78.

Pour me convaincre que le nombre d’appel pour F(n) n’était pas de l’ordre de grandeur de 2**n et que la suite des rapports était une suite monotone décroissante, sauf pour quelques petits nombres, j’ai écrit le code suivant:

F = [1, 1]
for n in range(2, 100+1):
    F.append(F[-1]+F[-2]+1)
m = 4   # Arbitraire
for i in range(len(F)):
    z = F[i] / 2**i
    if z > m: print(i)
    m = z
print(m)

Qui donne

2                                                                                                                       
9.04267854108422e-10                                                                                                     

Pour 1 j’ai 1/2 et pour 2 j’ai 3/4. Mais ça décroit par la suite.

Ta fonction récursive ne fait pas de mise en cache, donc tu la rappelles 2 fois par appel, d’où l’introduction d’un facteur exponentiel.
Essaie de regarder comment évolue la valeur de c quand tu calcules des valeurs de plus en plus grandes.

>>> c = 0; fibo(1); c
1
1
>>> c = 0; fibo(2); c
1
3
>>> c = 0; fibo(3); c
2
5
>>> c = 0; fibo(4); c
3
9
>>> c = 0; fibo(5); c
5
15
>>> c = 0; fibo(6); c
8
25
>>> c = 0; fibo(7); c
13
41
>>> c = 0; fibo(8); c
21
67
>>> c = 0; fibo(9); c
34
109
>>> c = 0; fibo(10); c
55
177

On voit clairement que le nombre d’appels suit une progression exponentielle, d’un facteur qui tend vers 1,618¹ environ (donc 2).

Tu as globalement raison @PierrotLeFou, parce qu’il y a toujours moins de terme à évaluer dans la "branche" $F(N-2)$ que dans la "branche" $F(n-1)$.

Ceci dit, ça n’enlève pas au fait que l’évolution du problème est essentiellement exponentielle. D’ailleurs, comme dit ici,

Le nombre d’appel pour calculer le nombre de Fibonacci $F(n)$ est de $2F(n)-1$.

Or, $F(n)\propto \phi^n$ (à un préfacteur près). Ce n’est certes pas $2^n$, mais c’est pas fou quand même

EDIT: grillé par @entwanne

Je voulais surtout illustrer ce que tout le monde sait, que la récursivité n’est pas conseillée (voire totalement déconseillée) pour calculer les nombres de Fibonacci.

Et que j’ai trouvé un moyen facile, pour ce cas, de calculer le nombre d’appels en récursivité.

Autour de 1000, le facteur d’exponentiation est 1.618033988749895

Ce facteur 1.618…, si tu lis le message de Pierre_24, c’est le nombre 'caché' sous la lettre grecque Phi. Et si tu regardes d’autres messages de cette discussion, tu verras qu’on parle du nombre d’or.

Au fait, c’est quoi, ce nombre d’or, il vaut combien ? Regardons Wikipedia

Effectivement:

>>> (1+5**0.5)/2                                                                                                        
1.618033988749895                                                                                                        

Merci pour la précision.

Pour être un peu exhaustif sur le sujet, comme un entre-deux entre la formule de Binet mentionnée par pierre_24 (et ses éventuels problèmes de précision des flottants), et la méthode itérative qui consiste à faire de l’ordre de $n$ opérations pour calculer $F_n$, il y a une approche naturellement récursive quand même intéressante et exacte, à base d’exponentiation rapide d’une matrice bien choisie¹, qui permet de descendre vers les $\log n$ opérations (et appels récursifs en l’occurence) pour calculer $F_n$.

Je pense que c’est intéressant à mentionner car c’est un principe que tu peux appliquer à la plupart des suites récurrentes linéaires. Et par exemple, si tu veux calculer quelque chose comme $F_{2022^{2023}} \mod 2024$, c’est sans doute l’approche la plus saine (bon j’admets que ça a l’air un peu artificiel comme demande, mais typiquement à la Project Euler ou autre exercice de programmation)

¹ je te laisse regarder pourquoi ça peut être intéressant de considérer la matrice $\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$ et sa mise à la puissance $n$ par exemple

Au passage, on peut aussi faire récursivement le calcul de fib(n) en temps logarithmique (contre exponentiel par la méthode stupide consistant à traduire directement la définition). Ce qui est bien meilleur que la version itérative naïve, qui est linéaire.

L’idée de base, c’est que si on connaît x = fib(n) et y = fib(n+1), on peut en tirer fib(2n) et fib(2n+1).

Exercice : trouver les formules, qui dérivent du problème "calculer la puissance n-ieme de la matrice du message ci-dessus"

La conclusion, c’est que la programmation récursive ne donne pas par essence des programmes moins efficaces. Faut juste pas faire n’importe quoi avec, comme la programmation itérative.

Le problème c’est la manière souvent débile d’enseigner la récursivité :

1. commencer par factorielle,

• 1.a concrètement personne n’a rien à péter de cette fonction. Erreur 1: faut donner des exemples motivants.
• 1.b dont la programmation itérative ne pose pas aucun problème, et est donc considérée comme la manière naturelle de faire (le produit des nombres de 1 à n => hop on fait une boucle de 1 à n). Erreur 2: aucune raison de se casser le cul à apprendre à faire autrement que ce qu’on sait déjà très bien faire

2. Continuer par fibonacci naïf

• 2.a Tout le monde s’en fout de fibonacci (erreur 1 again)
• 2.b on l’a déjà fait en itératif (erreur 2 again)
• 2.c ça marche pas pour les "grandes" valeurs, temps de calcul exponentiel. Erreur 3 : se casser la baraque tout seul en montrant que le truc qu’on enseigne, ça fait pas le boulot.

On y rajoutera "oui mais quand ça marche, ça explose la pile", avec la fonction d’Ackerman.