Méthode de Fibonacci

C'est la suite bien connue:

xn = (xn-1 + xn-2) mod m

Cette méthode est un cas particulier des générateurs à congruence additive:

avec un ensemble initial de nombres x0, x1, x2, x3, ..., xk-1,   et pour n=k, k+1, k+2, ...

xn = (xn-1 + xn-k) mod m

Cette méthode présente deux inconvénients:

Cycles

Pour k=1, un cycle apparaît dès qu'une paire de nombres consécutifs apparaît pour la deuxième fois: on voit dans l'exemple ci-dessous (en rouge les deux germes) qu'un même chiffre peut apparaître plusieurs fois avant l'apparition d'un cycle.


Expérience

Utilisez le programme javascript ci-dessous pour vous familiariser avec la méthode de Fibonacci. Entrez les germes, le modulo et la longueur de la séquence pseudo-aléatoire.

Essayez les valeurs suivantes et commentez:

Germe 1 Germe 2 Modulo
1 1 50
20 30 100
42 7 49
5 15 90
6 42 72



Germe 1:

Germe 2:

Modulo:

Longueur :


Séquence pseudo-aléatoire


Didier Müller, 28.12.02