Namide

Pseudo-aléatoire avec Fibonacci

C'est en cherchant le moyen le plus rapide et le plus efficace d'obtenir des séries de nombres aléatoires que j'ai découvert que Fibonacci est notre ami ! Comment une graine peut-elle générer une série de nombres aléatoires tandis qu'une autre tirerait une série complètement différente ? Fibonacci, à toi !

Bruit

Dans After Effect, on peut utiliser une fonction générant des nombres aléatoires random() dont la suite sera toujours la même. Si ce n'avait pas été le cas à chaque rendu les vidéos obtenues seraient différentes. Si l'on veut changer la suite de nombres aléatoires, il faut utiliser une graine : seed seedRandom( notreNouvelleGraine ). J'utilise souvent la fonction Math.random() en Flash pour mes animations et j'aurais aimé qu'elle me génère à chaque fois la même suite de nombres de la même manière que la fonction random() de After Effect. (Ci-contre, un bruit généré par la fonction Math.random() native de Flash.)

Bruit généré par un Math.random()
Bruit généré par un Math.random().

C'est pour cette raison que j'ai voulu développer un générateur de nombres pseudo-aléatoires qui respectait ces conditions :

Pour tester l'efficacité de ce générateur, je me fonde sur deux facteurs : sa vitesse de calcul et la dispersion des résultats. Pour tester cette dernière, je m'inspire de la méthode de Monte-Carlo : je vérifie que la moyenne de la somme des nombres obtenus se rapproche le plus possible de la médiane entre le maximum et le minimum que l'on peut obtenir. Par exemple, pour une grande suite de nombres pouvant aller chacun de 0 à 999, je regarde si la moyenne est bien proche de 500. Plus elle est proche de 500, plus cela signifie que la suite distribue équitablement les nombres.

J'ai tenté de coder plusieurs algorithmes à partir de quelques types de générateurs de nombres pseudo-aléatoires (middle-square de John von Neumann, des générateurs congruentiels linéaires…) et le plus concluant selon moi (plus rapide avec une meilleure dispersion des nombres) est la méthode de Fibonacci.

La suite de Fibonacci vérifie cette formule : U(n+2) = U(n) + U(n+1), c'est-à-dire qu'un nombre de la suite est la somme des deux nombres qui le précèdent. Voici le début de cette suite : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610…

La fonction n'est donc pas difficile à créer :

// Nombre U(n-1) de la suite de la méthode de Fibonacci
private var _nbre_f1:Number = 0;
// Nombre actuel U(n) de la suite de la méthode de Fibonacci
private var _nbre_f2:Number = 1;

public function fibonacci( mod:int ):Number
{
	// Calcul du nombre suivant selon la suite de Fibonacci
	var nbreSuiv:Number = this._nbre_f1 + this._nbre_f2;

	// Décalage des résultats
	this._nbre_f1 = this._nbre_f2;
	// Décalage des résultats
	this._nbre_f2 = nbreSuiv;

	// sortie avec un modulos
	return this._nbre_f2 % mod;
}

Maintenant j'y inclus une graine. La subtilité de cette suite est déterminée par les deux premiers nombres qu'on lui donne. Pour obtenir la suite de Fibonacci les deux premiers nombres sont 0 et 1.

Si l'on teste l'algorithme avec deux nombres quelconques au départ, il peut se passer des résultats étonnants : la suite ne réussi plus le test de Monte-Carlo. Par exemple, avec au départ deux multiples de 5 (10 et 15), nous obtenons cette suite : 10, 15, 25, 40, 65, 105, 170, 275… Les résultats sont tous des multiples de 5 !

Par contre, deux nombres (1 et un nombre entier quelconque) ne donneront pas (d'après mes tests) de suite ne réussissant pas le test de Monte-Carlo.

Voici donc comment initialiser la suite (démarrant avec 1 et x) à partir d'une graine :

// graine générale
private var _seed:uint = 0;
// Nombre U(n-1) de la suite de la méthode de Fibonacci
private var _nbre_f1:Number = 0;
// Nombre actuel U(n) de la suite de la méthode de Fibonacci
private var _nbre_f2:Number = 1;

public function set seed(input:uint):void
{
	this._seed = input;

	this._nbre_f1 = 1;
	// si la graine = 0 alors on a la suite de Fibonacci exacte
	this._nbre_f2 = input;
}

On se rend compte que répétés, les résultats finissent par tendre vers l'infini. Il faut donc relancer la suite tout en évitant d'obtenir la même liste de chiffres. Pour cela je me contente de recommencer le calcul en incrémentant la graine. Cette technique n'est pas la plus efficace (car après une boucle, la graine lancera elle-même la même suite de nombres, comme si l'on avait commencé par celle-ci) mais elle me semble la plus rapide à calculer.

package
{
	/**
	 * Génération de nombres pseudo aléatoire contrôlés afin d'être regénéré au plaisir.
	 *
	 * Une graine permet de changer le tirage, chaque tirage comportera la même suite.
	 *
	 * @langversion ActionScript 3.0
	 * @playerversion Flash 9
	 *
	 * @author   Damien
	 */
	public class Random
	{

		// graine générale à toutes les méthodes d'aléatoire = uint (petit de préférence)
		private var _seed:uint = 0;

		// id du chiffre actuel de la méthode de Fibonacci
		private var _nbre_f0:uint = _seed + 1;

		// Chiffre U(n-1) de la méthode de Fibonacci
		private var _nbre_f1:Number = 0;

		// Chiffre actuel de la méthode de Fibonacci : U(n)
		private var _nbre_f2:Number = 1;

		// Nombre de boucle faites sur la suite de Fibonnaci (à cause d'un maximum atteind)
		private var _nbre_f3:Number = 0;

		// graine générale à toutes les méthodes d'aléatoire = uint (petit de préférence)
		private static var SEED:uint = 0;

		// id du chiffre actuel de la méthode de Fibonacci
		private static var NBRE_F0:uint = SEED + 1;

		// Chiffre U(n-1) de la méthode de Fibonacci
		private static var NBRE_F1:Number = 0;

		// Chiffre actuel de la méthode de Fibonacci : U(n)
		private static var NBRE_F2:Number = 1;

		// Nombre de boucle faites sur la suite de Fibonnaci (à cause d'un maximum atteind)
		private static var NBRE_F3:Number = 0;

		public function Random(input:uint = 0) // input:uint = SEED
		{
			if(input > 0) seed = uint(input);
		}

		/**
		 * Source de la suite (statique et non statique).
		 * Le générateur peut commencer dans un état quelconque (la « graine »).
		 * Il produira toutefois la même suite si la graine reste identique.
		 *
		 * @param    input      la graine à implémenter en uint, par défaut elle a la valeur 0
		 */
		public function set seed(input:uint):void
		{
			this._seed = input;

			this._nbre_f1 = 1;

			// si input = 0 alors on a la suite de Fibonacci exacte
			this._nbre_f2 = input;

			// incrémentation du nombre d'itérations
			this._nbre_f0 = input;

			// initialisation du nombre de boucles
			this._nbre_f3 = 0;

		}
		public function get seed():uint
		{
			return this._seed;
		}

		public static function set seed(input:uint):void
		{
			SEED = input;

			NBRE_F1 = 1;

			// si input = 0 alors on a la suite de Fibonacci exacte
			NBRE_F2 = input;

			// incrémentation du nombre d'itérations
			NBRE_F0 = input;

			// initialisation du nombre de boucles
			NBRE_F3 = 0;

		}
		public static function get seed():uint
		{
			return SEED;
		}

		public function fibonacci(mod:int = 1000):Number
		{

			// Si la graine est trop élevée les résultats se rapprochent de l'infinis, on les redéfinis
			if(this._nbre_f1 == Infinity && this._nbre_f2 == Infinity)
			{
				// incrémentation du nombre de boucle
				this._nbre_f3++;

				// recommence une boucle
				this._nbre_f1 = 1;

				// fausse le second nombre en "salant" avec la boucle
				// tout en gardant un nombre premier issus de la suite de Fibonacci
				this._nbre_f2 = this._nbre_f3
			}

			// Calcul du nombre suivant selon la suite de Fibonacci
			var nbreSuiv:Number = this._nbre_f1+this._nbre_f2;

			// Si le prochain résultat se rapproche de l'infinis
			if(nbreSuiv == Infinity)
			{
				// incrémentation du nombre de boucle
				this._nbre_f3++;

				// recommence une boucle
				this._nbre_f1 = 1;

				// fausse le second nombre en "salant" avec la boucle
				// tout en gardant un nombre premier issus de la suite de Fibonacci
				this._nbre_f2 = this._nbre_f3;

				// Calcul du nombre suivant selon la suite de Fibonacci
				nbreSuiv = this._nbre_f1+this._nbre_f2;
			}

			// incrémentation du nombre d'itérations de la suite
			this._nbre_f0++;

			// Décalage des résultats
			this._nbre_f1 = this._nbre_f2;

			// Décalage des résultats
			this._nbre_f2 = nbreSuiv;

			// sortie avec un modulos
			return this._nbre_f2 % mod;
		}
		public static function fibonacci(mod:int=1000):Number
		{

			// Si la graine est trop élevée les résultats se rapprochent de l'infinis, on les redéfinis
			if(NBRE_F1 == Infinity && NBRE_F2 == Infinity)
			{
				// incrémentation du nombre de boucle
				NBRE_F3++;

				// recommence une boucle
				NBRE_F1 = 1;
				// fausse le second nombre en "salant" avec la boucle
				// tout en gardant un nombre premier issus de la suite de Fibonacci
				NBRE_F2 = NBRE_F3;
			}

			// Calcul du nombre suivant selon la suite de Fibonacci
			var nbreSuiv:Number = NBRE_F1 + NBRE_F2;

			// Si le prochain résultat se rapproche de l'infinis
			// on redéfinis les résultats et on "casse" la suite de Fibonacci
			if(nbreSuiv == Infinity)
			{
				// incrémentation du nombre de boucle
				NBRE_F3++;

				// recommence une boucle
				NBRE_F1 = 1;

				// fausse le second nombre en "salant" avec la boucle
				// tout en gardant un nombre premier issus de la suite de Fibonacci
				NBRE_F2 = NBRE_F3;

				// Calcul du nombre suivant selon la suite de Fibonacci
				nbreSuiv = NBRE_F1 + NBRE_F2;
			}

			// incrémentation du nombre d'itérations de la suite
			NBRE_F0++;

			// Décalage des résultats
			NBRE_F1 = NBRE_F2;

			// Décalage des résultats
			NBRE_F2 = nbreSuiv;

			// sortie avec un modulos
			return NBRE_F2 % mod;
		}

	}

}
Bruit pseudo-aléatoire
Bruit généré par un Random.fibonacci() avec une graine ayant pour valeur 84 252.
Bruit généré par un Random.fibonacci() avec une graine = 0
Bruit généré par un Random.fibonacci() avec une graine ayant pour valeur 0.

Attention, cet algorithme n'est pas aussi performant (d'un point de vue de la rapidité et des résultats obtenus) que Math.random() natif de Flash. Sur le graphique à gauche, nous pouvons apercevoir que le bruit qu'il génère, si l'on utilise une graine trop petite, laisse à intervalles réguliers des traces. En effet, une petite graine entraîne une progression plus lente des nombres au début et au moment des boucles ; il en résulte des nombres croissant dont la valeur est très proche les unes des autres.

Sur la dernière image nous pouvons voir ce que donne notre algorithme avec une graine de 84 252.

"Quiconque considère des méthodes arithmétiques pour produire des nombres aléatoires est, bien sûr, en train de commettre un péché."
John von Neumann.