264
8 G´ en´ erateurs de nombres al´ eatoires
(Voir, par exemple, [1] pour la description de tests de base pour les g´ en´ erateurs de
nombres al´ eatoires.) Il n’est donc pas surprenant que certains g´ en´ erateurs offerts par
les langages de programmation deviennent rapidement d´ esuets. L’histoire du langage
C est int´ eressante sur ce point. Le langage a ´ et´ e d´ evelopp´ e au d´ ebut des ann´ ees 70, et
le premier manuel de Kernighan et Ritchie, les p` eres du langage, a paru en 1978. `
A
cause de son grand succ` es, la n´ ecessit´ e d’un standard s’est vite fait sentir. Le processus
a ´ et´ e ardu mais, en 1989, l’American National Standards Institute (ANSI) ´ etablissait
une norme standardisant le langage. Dans les premi` eres versions, la fonction rand()
offerte par le langage avait un cycle de 2
15
− 1 = 32 767, une p´ eriode fort courte, certainement trop courte pour l’utilisation dans les jeux de hasard. Le standard ANSI
ne fixait pas la fonction rand() ; il se limitait ` a demander que le g´ en´ erateur produise
des entiers dans l’ensemble {0, 1, . . . , RAND MAX} et que RAND MAX soit au moins ´ egal `
a
32 767. Ainsi les divers compilateurs C respectant le standard ANSI de 1989 peuvent
avoir des fonctions rand() diff´ erentes, ou de RAND MAX et de p´ eriodes diff´ erents et un
mˆ eme programme, compil´ e sur diverses machines, peut produire des r´ esultats diff´ erents
mˆ eme pour des conditions initiales identiques. Les fonctions rand() de plusieurs compilateurs sont connues pour leurs pi` etres r´ esultats, c’est-` a-dire qu’elles ´ echouent `
a certains
tests statistiques jug´ es fondamentaux. Les concepteurs de ces compilateurs ne sont pas
n´ ecessairement ` a condamner ; cet ´ etat de fait montre plutˆ ot que la recherche dans ce
domaine est encore active.
8.6 Exercices
1.
Montrer que, si on g´ en` ere une suite de bits ind´ ependants (par exemple en
lan¸ cant une pi` ece de monnaie) et si on les regroupe par blocs de longueur r, lesquels repr´ esentent l’expression binaire (de gauche ` a droite) de nombres entiers de
S = {0, 1, . . . , 2
r−1
}, alors chaque entier apparaˆ ıt en moyenne une fois sur 2
r .
2. Le g´ en´ erateur lin´ eaire congruentiel g´ en` ere des nombres de E = {1, . . . , p − 1} par
la r` egle
x n = ax n−1 (mod p),
o` u p premier et a est tel que
a
k
≡ / 1 (mod p),
k
p−1
≡ 1.
(L’existence d’un tel a, appel´ e racine primitive de F p (Z p ), est d´ emontr´ ee au
th´ eor` eme 7.22 du chapitre 7.)
a) Soit p = 11. Trouver les racines primitives de F 11 (il y en a quatre).
b) Montrer que, quel que soit x 0 ∈ S, ce g´ en´ erateur produit une suite p´ eriodique
de p´ eriode exactement p − 1.
8 G´ en´ erateurs de nombres al´ eatoires
(Voir, par exemple, [1] pour la description de tests de base pour les g´ en´ erateurs de
nombres al´ eatoires.) Il n’est donc pas surprenant que certains g´ en´ erateurs offerts par
les langages de programmation deviennent rapidement d´ esuets. L’histoire du langage
C est int´ eressante sur ce point. Le langage a ´ et´ e d´ evelopp´ e au d´ ebut des ann´ ees 70, et
le premier manuel de Kernighan et Ritchie, les p` eres du langage, a paru en 1978. `
A
cause de son grand succ` es, la n´ ecessit´ e d’un standard s’est vite fait sentir. Le processus
a ´ et´ e ardu mais, en 1989, l’American National Standards Institute (ANSI) ´ etablissait
une norme standardisant le langage. Dans les premi` eres versions, la fonction rand()
offerte par le langage avait un cycle de 2
15
− 1 = 32 767, une p´ eriode fort courte, certainement trop courte pour l’utilisation dans les jeux de hasard. Le standard ANSI
ne fixait pas la fonction rand() ; il se limitait ` a demander que le g´ en´ erateur produise
des entiers dans l’ensemble {0, 1, . . . , RAND MAX} et que RAND MAX soit au moins ´ egal `
a
32 767. Ainsi les divers compilateurs C respectant le standard ANSI de 1989 peuvent
avoir des fonctions rand() diff´ erentes, ou de RAND MAX et de p´ eriodes diff´ erents et un
mˆ eme programme, compil´ e sur diverses machines, peut produire des r´ esultats diff´ erents
mˆ eme pour des conditions initiales identiques. Les fonctions rand() de plusieurs compilateurs sont connues pour leurs pi` etres r´ esultats, c’est-` a-dire qu’elles ´ echouent `
a certains
tests statistiques jug´ es fondamentaux. Les concepteurs de ces compilateurs ne sont pas
n´ ecessairement ` a condamner ; cet ´ etat de fait montre plutˆ ot que la recherche dans ce
domaine est encore active.
8.6 Exercices
1.
Montrer que, si on g´ en` ere une suite de bits ind´ ependants (par exemple en
lan¸ cant une pi` ece de monnaie) et si on les regroupe par blocs de longueur r, lesquels repr´ esentent l’expression binaire (de gauche ` a droite) de nombres entiers de
S = {0, 1, . . . , 2
r−1
}, alors chaque entier apparaˆ ıt en moyenne une fois sur 2
r .
2. Le g´ en´ erateur lin´ eaire congruentiel g´ en` ere des nombres de E = {1, . . . , p − 1} par
la r` egle
x n = ax n−1 (mod p),
o` u p premier et a est tel que
a
k
≡ / 1 (mod p),
k
p−1
≡ 1.
(L’existence d’un tel a, appel´ e racine primitive de F p (Z p ), est d´ emontr´ ee au
th´ eor` eme 7.22 du chapitre 7.)
a) Soit p = 11. Trouver les racines primitives de F 11 (il y en a quatre).
b) Montrer que, quel que soit x 0 ∈ S, ce g´ en´ erateur produit une suite p´ eriodique
de p´ eriode exactement p − 1.