Générateurs à congruence linéaire

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 :

x_n+1 = (a·x_n + c) mod m

avec a (multiplicateur), c (incrément), x₀ (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 x₀.
Si on préfère que la séquence soit toujours différente, on initialise x₀ 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.

Didier Müller, 2.1.03