$Bruit$

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 !

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 :

il doit avoir une graine qui correspond à une suite de nombres : si la même graine est utilisée, les suites de nombres doivent rester les mêmes. Par contre, chaque graine doit entraîner une suite de nombres différents ;
la fonction doit rester très légère en calcul afin de minimiser les ressources du processeur, surtout si l'on doit générer de grandes suites de nombres en peu de temps.

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   Namide
    */
  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.