Chapitre 10 • Simulation
388
Par qua lité du géné ra teur, on entend :
• l’équi répartition des chiffres dans les séquences obte nues en met tant bout à
bout les nombres pseudo aléatoires géné rés (chaque chiffre ayant la pro ba bi lité
1/10 d’appa ri tion). Mais une séquence telle que 111122223333... satis fe rait à ce
test d’équi répartition. Or, avec cette séquence, il ne s’agit pas de nombres au
hasard ! C’est pour quoi, on pra tique des tests por tant les fré quences d’appa ri tion
des « paires » (deux chiffres égaux consé cu tifs) ou encore des « bre lans » (trois
chiffres consé cu tifs). Plus géné ra le ment, on nomme cette famille de tests, les tests
du « poker » ;
• d’autre part, par leur nature, les pro cé dés de géné ra tion de nombres pseudoaléa toires, comme nous le ver rons plus bas, cyclent néces sai re ment au bout d’un cer
tain nombre d’ité ra tions nommé « période » du géné ra teur. Un bon géné ra teur doit
avoir une période suf fi sam ment longue.
De nom breux tests sta tistiques existent, per met tant de s’assu rer de la qua lité
d’un géné ra teur en termes de cor ré la tion et d’équi répartition ; test du χ
2
, test de
Kolmogorov Smirnov, test des inter valles, test du poker... Aucun de ces tests ne peut
être déter mi nant à lui seul. Cer taines suites de nombres pseudoaléa toires « fran
chissent » mieux cer tains tests que d’autres. Un géné ra teur de bonne qua lité doit
« fran chir » plu sieurs tests simul ta né ment.
Méthodes congruentielles
Elles regroupent plu sieurs méthodes basées sur les rela tions de congruence. Ce sont
les plus uti li sés, voici les prin ci pales. Rap pe lons que tous les nombres ci dessous
sont des entiers posi tifs.
• Méthode multiplicative
U k 5 a # U k21 (modulo m) où U 0 est la racine (seed) ; m est le divi seur (terme de
congruence) et a est le mul ti pli ca teur. On rap pelle que la congruence modulo m
revient à prendre le reste de la divi sion entière de l’entier a # U k21 par l’entier m.
Les nombres ainsi géné rés sont indé pen dants et uni for mé ment dis tri bués dans
l’inter valle [0, m[. La période Τ maximale de ce géné ra teur ne peut à l’évi dence
dépas ser m (le reste de la divi sion entière par m ne peut dépas ser m).
Ainsi : pour U k 5 a
k # U 0 (modulo m), on a : Τ 5 min{l / a
l 5 1 (modulo m)}.
On dira que a est une racine pri mi tive de m si Τ 5 m 2 1.
Exemple.
Cet exemple est choisi volontairement petit ; en pratique m est très grand.
Avec U 0 5 2, a 5 3, m 5 5, il vient :
U 0 5 2, U 1 5 1, U 2 5 3, U 3 5 4, U 4 5 2, c
Dans cet exemple a est bien une racine pri mi tive de m puisque T = m – 1 = 4.
388
Par qua lité du géné ra teur, on entend :
• l’équi répartition des chiffres dans les séquences obte nues en met tant bout à
bout les nombres pseudo aléatoires géné rés (chaque chiffre ayant la pro ba bi lité
1/10 d’appa ri tion). Mais une séquence telle que 111122223333... satis fe rait à ce
test d’équi répartition. Or, avec cette séquence, il ne s’agit pas de nombres au
hasard ! C’est pour quoi, on pra tique des tests por tant les fré quences d’appa ri tion
des « paires » (deux chiffres égaux consé cu tifs) ou encore des « bre lans » (trois
chiffres consé cu tifs). Plus géné ra le ment, on nomme cette famille de tests, les tests
du « poker » ;
• d’autre part, par leur nature, les pro cé dés de géné ra tion de nombres pseudoaléa toires, comme nous le ver rons plus bas, cyclent néces sai re ment au bout d’un cer
tain nombre d’ité ra tions nommé « période » du géné ra teur. Un bon géné ra teur doit
avoir une période suf fi sam ment longue.
De nom breux tests sta tistiques existent, per met tant de s’assu rer de la qua lité
d’un géné ra teur en termes de cor ré la tion et d’équi répartition ; test du χ
2
, test de
Kolmogorov Smirnov, test des inter valles, test du poker... Aucun de ces tests ne peut
être déter mi nant à lui seul. Cer taines suites de nombres pseudoaléa toires « fran
chissent » mieux cer tains tests que d’autres. Un géné ra teur de bonne qua lité doit
« fran chir » plu sieurs tests simul ta né ment.
Méthodes congruentielles
Elles regroupent plu sieurs méthodes basées sur les rela tions de congruence. Ce sont
les plus uti li sés, voici les prin ci pales. Rap pe lons que tous les nombres ci dessous
sont des entiers posi tifs.
• Méthode multiplicative
U k 5 a # U k21 (modulo m) où U 0 est la racine (seed) ; m est le divi seur (terme de
congruence) et a est le mul ti pli ca teur. On rap pelle que la congruence modulo m
revient à prendre le reste de la divi sion entière de l’entier a # U k21 par l’entier m.
Les nombres ainsi géné rés sont indé pen dants et uni for mé ment dis tri bués dans
l’inter valle [0, m[. La période Τ maximale de ce géné ra teur ne peut à l’évi dence
dépas ser m (le reste de la divi sion entière par m ne peut dépas ser m).
Ainsi : pour U k 5 a
k # U 0 (modulo m), on a : Τ 5 min{l / a
l 5 1 (modulo m)}.
On dira que a est une racine pri mi tive de m si Τ 5 m 2 1.
Exemple.
Cet exemple est choisi volontairement petit ; en pratique m est très grand.
Avec U 0 5 2, a 5 3, m 5 5, il vient :
U 0 5 2, U 1 5 1, U 2 5 3, U 3 5 4, U 4 5 2, c
Dans cet exemple a est bien une racine pri mi tive de m puisque T = m – 1 = 4.