Les générateurs de nombres pseudo-aléatoires font partie des algorithmes fondamentaux de l'informatique, même si leur fonctionnement est aujourd'hui beaucoup moins souvent expliqué dans les ouvrages modernes qu'il ne l'était autrefois. Pourtant, derrière une fonction aussi courante que rand() ou les générateurs de la bibliothèque standard du C++, se cache un algorithme mathématique relativement simple produisant une longue suite de valeurs qui semblent aléatoires, tout en étant parfaitement déterministes. Au cours de mes recherches, je n'ai trouvé que très peu de livres décrivant en détail le fonctionnement interne de ce type d'algorithme. L'une des rares références présentant une explication complète est l'ouvrage Algorithms (édition Addison-Wesley, 1983) de Robert Sedgewick, plus précisément les pages 33 à 44, qui décrivent différents procédés de génération pseudo-aléatoire.
Le programme C++ présenté ci-dessous s'inspire directement de cette approche. Il met en ouvre un générateur pseudo-aléatoire fondé sur des opérations arithmétiques simples et une multiplication adaptée aux grands entiers afin d'éviter certains dépassements de capacité. Chaque nouvel entier est calculé à partir de la valeur précédente selon une formule déterministe, produisant ainsi une séquence de nombres qui paraît aléatoire tout en restant parfaitement reproductible. Cette technique permet de mieux comprendre les principes de fonctionnement des anciens générateurs utilisés dans de nombreux langages de programmation avant l'apparition des algorithmes modernes :
- #include <iostream>
-
- int m=100000000;
- int ml=10000;
- int b=31415821;
- int a=1;
-
- int Mult(int p,int q) {
- int p1,p0,ql,q0;
- p1 = p / ml;
- p0 = p % ml;
- ql = q / ml;
- q0 = q % ml;
- return (((p0*ql+p1*q0) % ml)*ml+p0*q0) % m;
- }
-
- int Random() {
- a=(Mult(a,b)+1) % m;
- return a;
- }
-
- int main()
- {
- std::cout << "Génération de 10 nombres aléatoires statique:" << std::endl;
- for(int I=1;I<=10;I++) std::cout << Random() << std::endl;
- return 0;
- }
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
Comme la variable d'initialisation est fixée à la valeur 1 à chaque exécution du programme, la suite de nombres générée est rigoureusement identique d'un lancement à l'autre. Ce comportement est particulièrement utile pour les tests et le débogage, puisqu'il permet de reproduire exactement les mêmes résultats. En revanche, si l'on souhaite obtenir une séquence différente à chaque exécution, il suffit d'initialiser cette variable avec une valeur changeante, par exemple le résultat d'une fonction d'horloge telle que GetTickCount ou une autre source de temps système. On reproduit ainsi le principe du célèbre Randomize des anciens dialectes BASIC, où la graine du générateur était automatiquement initialisée à partir de l'horloge de l'ordinateur afin de produire une suite pseudo-aléatoire différente à chaque démarrage.