252
8 G´ en´ erateurs de nombres al´ eatoires
8.2 Le registre ` a d´ ecalage
Le registre ` a d´ ecalage (aussi ´ etudi´ e au chapitre 1) est un bon g´ en´ erateur de nombres
al´ eatoires. Il est constitu´ e d’un ruban de r cases contenant des entr´ ees a n−1 , . . . , a n−r ,
lesquelles sont des 0 ou des 1 (figure 8.1). Sur chacune de ces cases op` ere un q i ∈ {0, 1}
Fig. 8.1. Un registre `
a d´ ecalage
par multiplication, et les r´ esultats sont ensuite additionn´ es modulo 2. Les q i sont fix´ es et
caract´ erisent le g´ en´ erateur de nombres al´ eatoires. On g´ en` ere une suite pseudo-al´ eatoire
de la fa¸ con suivante.
• On se donne des nombres initiaux a 0 , . . . , a r−1 ∈ {0, 1} non tous nuls.
• ´
Etant donn´ e a n−r , . . . , a n−1 , le registre calcule l’´ el´ ement suivant comme suit :
a n ≡ a n−r q 0 + a n−r+1 q 1 + · · · + a n−1 q r−1 =
r−1
i=0
a n−r+i q i (mod 2).
(8.2)
• On d´ ecale chacune des entr´ ees vers la droite en oubliant a n−r . Le a n calcul´ e occupe
donc la case de gauche.
• On it` ere le proc´ ed´ e.
Dans la section 1.4 du chapitre 1, on montre que, si on choisit bien les q i et les
conditions initiales a 0 , a 1 , . . . , a r−1 , alors on g´ en` ere une suite de p´ eriode 2
r
− 1. Nous
reviendrons plus bas sur cette propri´ et´ e pour montrer comment on choisit les q i .
Exemple 8.4 Prenons le registre ` a d´ ecalage de quatre cases tel que (q 0 , q 1 , q 2 , q 3 ) =
(1, 1, 0, 0). Posons les conditions initiales (a 0 , a 1 , a 2 , a 3 ) = (0, 0, 0, 1). Alors, le registre
g´ en` ere la suite de p´ eriode 15
000100110101111
15
0001 . . .
Dans ce cycle de 15 entr´ ees, 0 est sorti sept fois et 1, huit fois. Regardons maintenant
les 15 sous-suites possibles de deux entr´ ees : 00 est sortie trois fois
8 G´ en´ erateurs de nombres al´ eatoires
8.2 Le registre ` a d´ ecalage
Le registre ` a d´ ecalage (aussi ´ etudi´ e au chapitre 1) est un bon g´ en´ erateur de nombres
al´ eatoires. Il est constitu´ e d’un ruban de r cases contenant des entr´ ees a n−1 , . . . , a n−r ,
lesquelles sont des 0 ou des 1 (figure 8.1). Sur chacune de ces cases op` ere un q i ∈ {0, 1}
Fig. 8.1. Un registre `
a d´ ecalage
par multiplication, et les r´ esultats sont ensuite additionn´ es modulo 2. Les q i sont fix´ es et
caract´ erisent le g´ en´ erateur de nombres al´ eatoires. On g´ en` ere une suite pseudo-al´ eatoire
de la fa¸ con suivante.
• On se donne des nombres initiaux a 0 , . . . , a r−1 ∈ {0, 1} non tous nuls.
• ´
Etant donn´ e a n−r , . . . , a n−1 , le registre calcule l’´ el´ ement suivant comme suit :
a n ≡ a n−r q 0 + a n−r+1 q 1 + · · · + a n−1 q r−1 =
r−1
i=0
a n−r+i q i (mod 2).
(8.2)
• On d´ ecale chacune des entr´ ees vers la droite en oubliant a n−r . Le a n calcul´ e occupe
donc la case de gauche.
• On it` ere le proc´ ed´ e.
Dans la section 1.4 du chapitre 1, on montre que, si on choisit bien les q i et les
conditions initiales a 0 , a 1 , . . . , a r−1 , alors on g´ en` ere une suite de p´ eriode 2
r
− 1. Nous
reviendrons plus bas sur cette propri´ et´ e pour montrer comment on choisit les q i .
Exemple 8.4 Prenons le registre ` a d´ ecalage de quatre cases tel que (q 0 , q 1 , q 2 , q 3 ) =
(1, 1, 0, 0). Posons les conditions initiales (a 0 , a 1 , a 2 , a 3 ) = (0, 0, 0, 1). Alors, le registre
g´ en` ere la suite de p´ eriode 15
000100110101111
15
0001 . . .
Dans ce cycle de 15 entr´ ees, 0 est sorti sept fois et 1, huit fois. Regardons maintenant
les 15 sous-suites possibles de deux entr´ ees : 00 est sortie trois fois