Un algorithme fort simple en apparence, mais devenu de plus en plus rare dans les ouvrages modernes de programmation, est celui du fonctionnement interne d'un générateur de nombres pseudo-aléatoires. Aujourd'hui, la plupart des programmeurs utilisent directement les fonctions fournies par leur langage ou leur bibliothèque favorite sans nécessairement chercher à comprendre les mécanismes mathématiques qui se cachent derrière celles-ci. Pourtant, pendant de nombreuses années, la conception d'un bon générateur aléatoire constituait un sujet important de l'informatique théorique et pratique, car de nombreux programmes, simulations et jeux reposaient sur la qualité des nombres produits.
Au cours de mes recherches dans divers livres consacrés aux algorithmes et aux mathématiques appliquées, je n'ai trouvé que très peu d'explications détaillées concernant la mise en oeuvre complète d'un tel générateur. L'une des rares références décrivant clairement cette technique est l'ouvrage ALGORITHMS publié en 1983 par Robert Sedgewick chez Addison-Wesley, plus particulièrement dans les pages 33 à 44. Ce livre présente notamment les principes des générateurs congruentiels linéaires, une famille d'algorithmes capables de produire de longues suites de nombres présentant une apparence aléatoire à partir d'une simple valeur initiale.
Il est toutefois important de comprendre que les nombres ainsi générés ne sont pas véritablement aléatoires. Ils sont plutôt qualifiés de pseudo-aléatoires, car leur séquence est entièrement déterminée par une valeur de départ appelée « graine » (seed). Si cette valeur demeure identique d'une exécution à l'autre, la suite de nombres obtenue sera exactement la même. Cette propriété est souvent utile pour reproduire des tests ou des simulations, mais elle peut également devenir un inconvénient lorsque l'on recherche un comportement imprévisible.
Le programme Delphi présenté ci-dessous s'inspire directement de ces principes classiques. Il montre comment générer une suite de nombres pseudo-aléatoires à l'aide d'opérations arithmétiques simples et d'une formule soigneusement choisie. Cette implémentation permet de mieux comprendre le fonctionnement interne des générateurs utilisés dans de nombreux logiciels avant l'apparition des bibliothèques modernes. À l'aide de ce code source, vous pourrez observer la séquence produite, analyser sa répétition et découvrir pourquoi l'utilisation d'une valeur provenant de l'horloge système, comme GetTickCount, permet d'obtenir des résultats différents à chaque exécution, reproduisant ainsi l'effet du célèbre Randomize Timer des anciens dialectes BASIC :
- Program RandomStatic;
-
- {$APPTYPE CONSOLE}
-
- Uses SysUtils;
-
- Const
- m=100000000;
- ml=10000;
- b=31415821;
- a:LongInt=1;
-
- Function Mult(p,q:LongInt):LongInt;
- Var
- pl,p0,ql,q0:LongInt;
- Begin
- pl:=p div ml;
- p0:=p mod ml;
- ql:=q div ml;
- q0:=q mod ml;
- Mult:=(((p0*ql+pl*q0) mod ml)*ml+p0*q0) mod m;
- End;
-
- Function _Random:LongInt;Begin
- a:=(Mult(a,b)+1) mod m;
- _Random:=a;
- End;
-
- Var
- I:Integer;
-
- BEGIN
- WriteLn('Génération de 10 nombres aléatoires statique:');
- For I:=1 to 10 do WriteLn(_Random);
- END.
on obtiendra le résultat suivant :
Génération de 10 nombres aléatoires statique:31415822
40519863
62952524
25482205
90965306
70506227
6817368
12779129
29199910
45776111
Le résultat est toujours le même parce que la variable «a» contient invariablement la valeur 1 à chaque démarrage du programme. Pour changer cette situation, il faudra donc affecter le résultat d'une fonction d'horloge, comme «GetTickCount», pour provoquer une effet de «Randomize Timer» du bon vieux BASIC.
Voir également
Langage de programmation - Delphi/Kylix/Lazarus - Référence de procédures et fonctions - Random
Science - Mathématique