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 (la graine du générateur).
Si on préfère plutôt que la séquence soit toujours différente, on initialise x0 avec une grandeur toujours différente, l'heure système par exemple (ce que fait la fonction randomize() du C).
Dans tous les cas, les nombres de la suite sont compris entre 0 et c-1.
Et ça marche bien ?
Imaginons à titre d'exemple qu'on choisisse a,b et c tels que :
xn+1 = ( 25 * xn + 16) mod 256
Pour x0 = 12, les nombres produits sont : 60 , 236 , 28 , 204 , 252 , 172 ....
Damned, ils sont tous pairs !!
Pour x0 = 11, les nombres produits sont : 35, 123 , 19 , 235 , 3 , 91 , 243 ..
ils sont tous impair ! ! !
Pour x0 = 10, les nombres produits sont : 10 ,10 ,10 ,10 ....
Bon sang, voilà qu'il est bloqué maintenant ! ! ! !
La formule est simple mais le choix des trois paramètres ne doit pas être fait à la légère.
Pour ne pas retrouver les défauts graves de notre petit exemple, il faut regarder cette suite d'un peu plus près. Si on choisi b non nul , il est toujours possible d'obtenir une période de longueur c (donc pas de risque de bloquage puisqu'on va retrouver tous les nombres entre 0 et c-1 dans la suite). D. Knuth fait la démonstration des critères que doivent remplir a,b et c pour cela :
* b et c doivent être premiers entre eux
* a-1 doit être un multiple de p, pour tout p nombre premier diviseur de c
* a-1 doit être un multiple de 4 si c est un multiple de 4.
* si c est une puissance de 2, le bit de poids faible des nombres produits vaut altérnativement 0 et 1 (ce n'est d'ailleurs pas le seul cas où cela se produit).
Partager