Générateurs à congruence linéaire (GCL)
Il s'agit de l'algorithme le plus utilisé pour produire des nombres aléatoires depuis qu'il a été inventé en 1948 par D. H. Lehmer. C'est la suite :
avec a (multiplicateur), c (incrément), x0 (germe), et m qui sont quatre nombres entiers non-négatifs.
- Si on désire produire toujours la même séquence (ce qui est pratique à des fins de tests), on rentre toujours la même valeur de x0.
- Si on préfère que la séquence soit toujours différente, on initialise x0 avec une grandeur toujours différente, l'heure système par exemple.
Dans tous les cas, les nombres de la suite sont compris entre 0 et m-1.
Expérience
Utilisez le programme javascript ci-dessous pour vous familiariser avec un générateur à conguence linéaire. Entrez le germe, a, c et le modulo m de la séquence pseudo-aléatoire.
 Essayez les valeurs suivantes et commentez:
| Germe |
a |
c |
m |
| 12 |
25 |
16 |
256 |
| 11 |
25 |
16 |
256 |
| 10 |
25 |
16 |
256 |
| 0 |
31415821 |
1 |
100000000 |
La formule est simple mais le choix des trois paramètres a, c et m ne doit pas être fait à la légère, comme on le verra ci-dessous.
|
|
|
Séquence pseudo-aléatoire
|
|
Critères de Knuth
 Si on choisi c non nul, il est toujours possible d'obtenir une période de longueur m (donc pas de risque de blocage puisqu'on va retrouver tous les nombres entre 0 et m-1 dans la suite). D. Knuth fait la démonstration des critères que doivent remplir a, c et m pour cela :
- c et m doivent être premiers entre eux
- a-1 doit être un multiple de p, pour tout p nombre premier diviseur de m
- a-1 doit être un multiple de 4 si m est un multiple de 4.
- si m est une puissance de 2, le bit de poids faible des nombres produits vaut alternativement 0 et 1 (ce n'est d'ailleurs pas le seul cas où cela se produit).
Si c=0, la situation est plus compliquée parce qu'il reste toujours la possibilité de blocage (si x0=0), donc la période du générateur ne peut être au mieux que m-1.
L'analyse dans le cas général est assez difficile, pour m = 2n avec n > 3 on peut dire que:
- a mod 8 doit être égal à 3 ou 5
- la période du générateur est 2(n-2) et tous les bits de poids faible des nombres produits sont identiques (il faut donc décaler le nombre produit de 1 vers la droite).
|
Pour ne pas retrouver les défauts graves de notre petit exemple, il faut regarder cette suite d'un peu plus près.
Pour notre second essai, soyons plus prudents et respectons scrupuleusement les critères précédents:
xn+1 = (31'415'821xn + 1) mod 100'000'000 (citée par R. Sedgewick)
On a bien respecté les critères de Knuth :
- 1 et 100'000'000 sont bien premiers entre eux. Par conséquent, on est certain qu'il n'y aura pas de problème de blocage ou de série de nombres tous pairs ou impairs. Tous les nombres entre 0 et 99'999'999 vont sortir et chacun une fois tous les 100'000'000 de tirages.
- 31'415'821 - 1 = 31'415'820 est bien un multiple de 2 et de 5 (les deux seuls nombres premiers qui divisent 100'000'000).
- C'est aussi un multiple de 4 (car 100 000 000 est lui-même un multiple de 4).
Regardons ce que ça donne, par exemple pour x0 = 0. Les nombres produits sont:
Vous ne remarquez rien ? Non? Alors surlignez la fin de cette ligne: Regardez le dernier chiffre.
Avoir la certitude que tous les nombres vont sortir ne suffit pas à garantir qu'ils seront suffisament aléatoires!
Quelques mauvais générateurs
Dans un article fameux, Park & Miller passent en revue de nombreux générateurs couramment utilisés et qui la plupart du temps présentent des défauts souvent assez graves. Citons en vrac:
Laissons la conclusion de tout ceci à Robert Sedgewick: «C'est une règle générale, les générateurs de nombres aléatoires sont délicats et doivent être traités avec respect. Il est difficile d'être certain qu'un générateur donné est bon sans investir d'énormes efforts dans des tests statistiques variés...».
Quelques bons générateurs
Afin d'éviter que n'importe qui propose un générateur pseudo-aléatoire sans savoir très bien ce qu'il fait (comme dans les exemples dramatiques précédents), Park & Miller ont proposé un générateur standard convenablement testé et dont le code est portable sur toutes les machines. Ils l'ont appelé le Standard minimal. Il est défini par:
| xn+1 = 16'807 xn mod (231- 1) |
D. Knuth recense dans «Seminumerical Algorithms» un certain nombre de générateurs congruentiels linéaires de qualité. S'il n'est pas possible d'utiliser le Standard minimal, on pourra essayer par exemple :
Exercice
 |
Programmez dans Mathematica les générateurs suivants:
- Standard minimal: xn+1 = 16807 xn mod (231- 1)
- RANDU: xn+1 = 65539 xn mod 231
Fonctions Mathematica utiles: AppendTo, For, Last, Mod, Module, N.
|
Vous produirez avec chacun de ces générateurs une liste de 100 nombres pseudo-aléatoires compris dans l'intervalle [0,1[.
| Le fichier Mathematica complet est disponible, mais seulement pour les visiteurs autorisés! |
|
|
Références
- Produire des nombres « au hasard », par Pierre Larbier, novembre 1994
- Linear Congruential Generator: LCG
- Knuth D. E., The Art of Computer Programming : Seminumerical Algorithms, chapter 3, Addison Wesley, 1981
- Park S. K., Miller K.W., Random Number Generators: Good Ones Are Hard To Find, Comm. of the ACM, Vol 31, 10, Oct. 1988, pp. 1192-1201
- Don Knuth's Home Page
Didier
Müller, 2.1.03