Vous savez surement lancer un dé ? Ça vous donne un nombre aléatoire entre 1 et 6. Rien de plus simple dans la réalité que de générer un nombre aléatoire. On utilise beaucoup les dés à 6 faces dans toutes sortes de jeu. On appelle ça un D6. Il existe aussi des dés à 20 faces, des D20, et on monte jusqu'à 100 faces même !
Bref, dans la réalité, on sait faire. Comment s'en sort l'informatique ? L'ordinateur ne lance pas un dé pour faire ça, ça prendrait trop de temps ! Certains algorithmes demandent des centaines de milliers de chiffres aléatoires à générer, il faut pouvoir les générer rapidement. Le plus connu est la
méthode Monte-Carlo, utile pour calculer des probabilités à de très grandes échelles.
Pour générer ces nombres, on ne va pas faire de l'aléatoire, mais du pseudo-aléatoire. C'est presque aléatoire, mais pas vraiment.
L'idée est de générer une simple suite de nombre, de la forme u
n = A u
n-1 + B.
On choisit un point de départ, u
0.
Ensuite, u
1 = A . u
0 + B
Puis u
2 = A . u
1 + B
etc...
Ainsi on généré la suite u
n : u
0, u
1, u
2.... Qui nous donne autant de nombre aléatoire que l'on veut !
Pour avoir des nombres qui imite le fonctionnement d'un dé, on va ajouter un modulo 6 pour être sur de rester entre 1 et 6, ce qui nous donne la formule d'un
générateur congruentiel linéaire :
un = [A un-1 + B] mod m
Et là, si vous avez suivi, vous avez envie de dire `
mais, la suite va toujours avoir la même tête pour le même u0`, et je vous répondrais que c'est vrai. u
0 est appelé la graine du générateur, ou `
seed` en anglais. Il faut pouvoir la choisir.... aléatoirement !
En pratique, on utilise souvent la date actuelle, ce qui suffit à avoir une génération assez aléatoire.
Enfin, les constantes A et B doivent être choisies pour obtenir les meilleurs suites aléatoires possibles. De nombreux mathématiciens se sont pencher sur le problème, au hasard, A = 31415821, B = 1 et C = 10
8, et on obtient le générateur de
Robert Sedgewick.
Il existe aussi d'autres formules pour créer la suite, d'autre choix de constante, mais
le principe de base est toujours le même, un élément de départ u0, puis une suite un = f(un-1).L'erreur que font la plupart des développeurs est de réinitialiser la graine trop souvent avec la même valeur. Si on initialise la suite selon la seconde actuelle, et qu'on lance l'algorithme 3 fois pendant la même seconde, et bien on tombera 3 fois sur le même résultat, pas super aléatoire.
La méconnaissance de la base de la génération des nombres pseudo-aléatoires amène beaucoup de suspicion et de crainte quand à leurs utilisations, alors qu'en pratique, c'est une simple suite mathématique !
Pour les plus développeurs d'entre vous, l'article de Microsoft sur l'utilisation de la classe Random en C# est concis avec un exemple très précis des erreurs à ne pas faire :
Random (Constructeur)La valeur initiale par défaut est dérivée de l'horloge système et a la résolution finie. En conséquence, les objets Random différents qui sont créés successivement par un appel au constructeur par défaut ont des valeurs initiales par défaut identiques et produisent ainsi des jeux identiques de nombres aléatoires. Ce problème peut être évité en utilisant un seul objet Random pour générer tous les nombres aléatoires. Vous pouvez également le contourner en modifiant la valeur de départ retournée par l'horloge système, puis en fournissant explicitement cette nouvelle valeur de départ au constructeur Random(Int32).
