Parmi les nombreux algorithmes fondamentaux de l'informatique, le générateur de nombres pseudo-aléatoires occupe une place particulièrement importante. Bien qu'il soit utilisé quotidiennement dans les jeux, les simulations, les statistiques, la cryptographie, les tests logiciels et de nombreuses applications scientifiques, son fonctionnement interne est rarement expliqué en détail dans les ouvrages modernes. La plupart des langages de programmation proposent aujourd'hui des fonctions toutes prêtes permettant d'obtenir des valeurs apparemment aléatoires, mais peu de programmeurs prennent le temps d'examiner les mécanismes mathématiques qui se cachent derrière ces fonctions. Pourtant, comprendre la manière dont un ordinateur produit une suite de nombres pseudo-aléatoires constitue un excellent exercice d'algorithmique et permet de mieux saisir les limites de ce type de génération.
Au cours de recherches effectuées dans plusieurs manuels de programmation et d'algorithmique, il est surprenant de constater que les descriptions détaillées de ces méthodes sont relativement rares. L'une des références les plus intéressantes sur le sujet demeure l'ouvrage ALGORITHMS, 1983, Edition Addison-Wesley, par Robert Sedgewick, page 33 à 44. Cet ouvrage présente plusieurs techniques permettant de construire des générateurs efficaces à partir d'opérations arithmétiques simples. Le programme présenté ci-dessous s'inspire directement de ces principes et illustre le fonctionnement d'un générateur congruentiel, une famille d'algorithmes qui a longtemps été utilisée dans de nombreux systèmes informatiques.
Le principe consiste à partir d'une valeur initiale appelée « graine » ou seed, puis à appliquer de manière répétée une formule mathématique produisant une nouvelle valeur à chaque appel. Les constantes choisies influencent directement la qualité statistique de la séquence obtenue. Dans cet exemple, une fonction de multiplication spécialisée est utilisée afin de limiter les risques de dépassement de capacité tout en conservant de bonnes propriétés de distribution. Chaque nouvel appel à la fonction de génération produit alors un nombre différent, donnant l'impression d'un comportement aléatoire alors que la suite est en réalité entièrement déterministe.
L'exécution du programme affiche dix nombres pseudo-aléatoires successifs. Toutefois, comme la variable servant de graine est initialisée à la même valeur lors de chaque démarrage, la séquence produite demeure toujours identique. Cette caractéristique est normale et constitue même un avantage dans certains contextes où l'on souhaite reproduire exactement les mêmes résultats. Lorsque l'on désire obtenir une séquence différente à chaque exécution, il devient nécessaire d'initialiser la graine à l'aide d'une source variable, comme l'horloge du système. Cette technique rappelle le célèbre « Randomize Timer » des anciens dialectes BASIC, qui permettait de varier automatiquement les suites générées. Ainsi, ce programme offre une excellente introduction aux principes mathématiques des générateurs pseudo-aléatoires et permet de mieux comprendre le fonctionnement des fonctions de génération intégrées aux bibliothèques modernes du langage C.
Voici un petit programme inspiré de se livre, permettant d'effectuer la génération de nombre aléatoire statique en C :
- #include <stdio.h>
- #include <stdlib.h>
-
- 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()
- {
- int I;
- printf("Génération de 10 nombres aléatoires statique:n");
- for(I=1;I<=10;I++) printf("%in",Random());
- 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
Le résultat est toujours le même parce que la variable «a» contient invariablement la valeur 1 à chaque démarrage du programme. Pour changer cette situation, il faudra donc affecter le résultat d'une fonction d'horloge, comme «GetTickCount», pour provoquer une effet de «Randomize Timer» du bon vieux BASIC.
Voir également
Langage de programmation - C - Référence de procédures et fonctions - rand
Science - Mathématique