Suite de Fibonacci : Récursivité, cryptographie et nombre d’or

-
3
 m de lecture
-

Dans le monde des mathématiques, l’importance des suites et séries en analyse n’est plus à prouver. Parfois, il est difficile de trouver une application concrète aux concepts inventés (ou découverts?) dans le domaine. La suite de Fibonacci, elle, se retrouve dans plusieurs pans de la nature et continue de fasciner les chercheurs grâce à ses propriétés étroitement liées au nombre d’or.

Histoire et contexte

La suite de Fibonacci tire son nom du mathématicien italien du XIIIème siècle, Leonardo de Pise, également connu sous le nom de Fibonacci. Bien qu’il n’ait pas inventé la suite, il l’a introduite en Europe avec son livre « Liber Abaci » (Livre de l’Abacus ou Livre du calcul) en 1202. Dans ce livre, Fibonacci posait et résolvait un problème impliquant la croissance d’une population de lapins idéalisée, qui conduit à cette séquence de nombres. Il convient de noter que la suite de Fibonacci était déjà connue bien avant cette date en Inde, où les relations entre les nombres de la suite étaient déjà étudiées.

Les nombres de Fibonacci ont de nombreuses applications dans la nature et dans l’art. Ils peuvent être observés à diverses échelles, des pétales de fleurs aux spirales de galaxies. Les pétales de fleurs ont souvent un nombre de Fibonacci – les marguerites peuvent avoir 34, 55 ou même 89 pétales. De plus, les graines de tournesols ou les pommes de pin sont souvent disposées en spirales suivant les nombres de Fibonacci.

En architecture, le nombre d’or, directement lié à la suite de Fibonacci, a été sollicité pour créer des œuvres qui sont agréables à l’œil grâce à leur proportion « parfaite ». Par exemple, le Parthénon en Grèce et le Taj Mahal en Inde semblent tous deux utiliser le nombre d’or dans leur construction.

C’est cette universalité qui rend la suite de Fibonacci si fascinante – une simple séquence de nombres qui trouve son chemin à travers les mathématiques, la nature et l’art, unissant des domaines qui pourraient sembler éloignés à première vue. Dans la section suivante, nous examinerons de plus près ce que sont ces nombres et comment nous pouvons les générer nous-mêmes à l’aide du langage de programmation Python.

Le chou de Romanesco cache un secret – comptez le nombre de spirales, si vous y arrivez !

Définition et implémentation

Formellement, la suite de Fibonacci est une suite dont chaque terme est égal à la somme des deux éléments qui le précèdent. La seule connaissance des deux premiers termes et de la formule de récurrence suffit pour construire la suite dans son intégralité.

$F_0 = 0$, $F_1 = 1$ et $F_n = F_{n-1}+ F_{n-2}$ pour $n \geq 2$

La construction d’un programme fournissant le n-ième nombre de Fibonacci est un très bon exercice élémentaire. Avant de poursuivre votre lecture, vous pouvez essayer de coder la fonction par vous-même !

Voici une fonction Python répondant au problème : 

				
					def fibonacci(n):
    if n in {0, 1}:
        return n
    return fibonacci(n-1) + fibonacci(n-2)
				
			

Cette première implémentation récursive peut être satisfaisante, mais il y a la possibilité d’optimiser ce code en optant pour une approche itérative. La récursivité est très restrictive en termes de temps de calcul ; en réalité, la complexité temporelle de cette fonction est en O(n²). En pratique, cela signifie que la fonction peine à fournir un résultat dans un délai satisfaisant lorsque n est grand (par exemple, n = 40) 

Voici une nouvelle approche cette fois-ci itérative, qui produit le même résultat à l’aide d’une boucle for :

				
					def fibonacci(n):
    a, b, c= 0, 1, 0
    if n == 0:
        return 0
    for i in range(2, n+1):
        c = a + b
        a = b
        b = c
    return b
				
			

Une manière d’optimiser ce code serait de garder en cache les éléments de la suite à mesure qu’ils sont introduits, de sorte à éviter les calculs redondants à chaque appel de la fonction. 

Additionnellement, il existe une formule mathématique permettant de calculer le terme exact de la suite sans passer par la récurrence. Appelée formule de Binet, elle fait appel au nombre d’or :

				
					def fibonacci(n):


    sqrt5 = math.sqrt(5)


    F_n = int((( (1 + sqrt5) ** n - (1 - sqrt5) ** n ) / ( 2 ** n * sqrt5 )))


    return F_n
				
			

Conclusion

On retrouve la suite de Fibonacci dans beaucoup de domaines très variés tels que la cryptographie ou en trading. En effet, elle permet entre autres de générer une liste de nombres pseudo-aléatoires ou de créer un système élémentaire de chiffrement. En finance, on utilise un outil appelé niveau de retracement de Fibonacci pour estimer jusqu’où un actif pourrait reculer avant de reprendre son mouvement de tendance. En analyse de séries temporelles, les nombres de Fibonacci sont utilisés pour déterminer le nombre optimal de périodes de temps à utiliser dans le calcul des moyennes mobiles.

Facebook
Twitter
LinkedIn

DataScientest News

Inscrivez-vous à notre Newsletter pour recevoir nos guides, tutoriels, et les dernières actualités data directement dans votre boîte mail.

Vous souhaitez être alerté des nouveaux contenus en data science et intelligence artificielle ?

Laissez-nous votre e-mail, pour que nous puissions vous envoyer vos nouveaux articles au moment de leur publication !

Newsletter icone
icon newsletter

DataNews

Vous souhaitez recevoir notre
newsletter Data hebdomadaire ?