262
8 G´ en´ erateurs de nombres al´ eatoires
u n =
⎧
⎨
⎩
m
j=1
δ j a n,j
p j
⎫
⎬
⎭
,
dans laquelle les δ j sont des entiers arbitraires relativement premiers avec les p j . Ici,
{x} repr´ esente la partie fractionnaire d’un nombre r´ eel x, c’est-` a-dire le nombre
{x} = x − [x],
o` u [x] est la partie enti` ere de x. Ce g´ en´ erateur de nombres al´ eatoires qui produit la suite
u n est appel´ e g´ en´ erateur r´ ecursif multiple combin´ e.
Remarque Dans la litt´ erature, on trouve aussi la notation x (mod 1) au lieu de {x}.
Mˆ eme si x et {x} ne sont pas des entiers, ceci est en accord avec la d´ efinition selon
laquelle deux nombres a et b sont congrus modulo un entier n si leur diff´ erence a − b est
de la forme mn pour un entier m ∈ Z.
Exemple 8.18 Nous consid´ erons un g´ en´ erateur r´ ecursif multiple combin´ e tel que r = 3,
m = 2, p 1 = 3, p 2 = 2 et δ 1 = δ 2 = 1. Nous laissons le lecteur v´ erifier que le polynˆ ome
Q 1 (x) = x
3
− x − 2 est primitif sur F 3 . Alors, la premi` ere r´ ecurrence lin´ eaire associ´ ee,
sous les conditions initiales 001, g´ en` ere la suite {a n } de p´ eriode 26 dans laquelle la
fenˆ etre suivante est r´ ep´ et´ ee :
00101211201110020212210222.
La deuxi` eme r´ ecurrence lin´ eaire est celle qui est associ´ ee au polynˆ ome Q 2 (x) = x
3
−x−1,
lequel est primitif sur F 2 , comme l’a montr´ e l’exemple 8.8. Alors, la r´ ecurrence lin´ eaire
associ´ ee, sous les conditions initiales 001 g´ en` ere la suite {a
n } de p´ eriode 7 dans laquelle
la fenˆ etre suivante est r´ ep´ et´ ee :
0010111.
Le g´ en´ erateur combin´ e a donc comme p´ eriode 7 × 26 = 182. Nous pr´ esentons ses sorties
par blocs de trois lignes : la premi` ere ligne de chaque bloc repr´ esente une p´ eriode de la
premi` ere r´ ecurrence lin´ eaire. La deuxi` eme ligne repr´ esente la suite correspondante a
n :
des traits verticaux s´ eparent les diff´ erentes fenˆ etres r´ ep´ etant la p´ eriode. La troisi` eme
ligne repr´ esente les sorties
an
3 +
a
n
2 . Toutes ces sorties ont ´ et´ e ´ ecrites en multiples de
1
6 pour mettre en ´ evidence le fait que les num´ erateurs forment une suite de nombres
al´ eatoires de {0, 1, . . . , 5}. Ainsi, le premier bloc repr´ esente n = 0, . . . , 25, le second
n = 26, . . . , 51, etc.
On voit que, si les nombres p i sont petits, la r´ egularit´ e des sorties des diff´ erents
nombres ou sous-suites n’apparaˆ ıt pas aussi rapidement que dans les r´ ecurrences F p -
lin´ eaires.
8 G´ en´ erateurs de nombres al´ eatoires
u n =
⎧
⎨
⎩
m
j=1
δ j a n,j
p j
⎫
⎬
⎭
,
dans laquelle les δ j sont des entiers arbitraires relativement premiers avec les p j . Ici,
{x} repr´ esente la partie fractionnaire d’un nombre r´ eel x, c’est-` a-dire le nombre
{x} = x − [x],
o` u [x] est la partie enti` ere de x. Ce g´ en´ erateur de nombres al´ eatoires qui produit la suite
u n est appel´ e g´ en´ erateur r´ ecursif multiple combin´ e.
Remarque Dans la litt´ erature, on trouve aussi la notation x (mod 1) au lieu de {x}.
Mˆ eme si x et {x} ne sont pas des entiers, ceci est en accord avec la d´ efinition selon
laquelle deux nombres a et b sont congrus modulo un entier n si leur diff´ erence a − b est
de la forme mn pour un entier m ∈ Z.
Exemple 8.18 Nous consid´ erons un g´ en´ erateur r´ ecursif multiple combin´ e tel que r = 3,
m = 2, p 1 = 3, p 2 = 2 et δ 1 = δ 2 = 1. Nous laissons le lecteur v´ erifier que le polynˆ ome
Q 1 (x) = x
3
− x − 2 est primitif sur F 3 . Alors, la premi` ere r´ ecurrence lin´ eaire associ´ ee,
sous les conditions initiales 001, g´ en` ere la suite {a n } de p´ eriode 26 dans laquelle la
fenˆ etre suivante est r´ ep´ et´ ee :
00101211201110020212210222.
La deuxi` eme r´ ecurrence lin´ eaire est celle qui est associ´ ee au polynˆ ome Q 2 (x) = x
3
−x−1,
lequel est primitif sur F 2 , comme l’a montr´ e l’exemple 8.8. Alors, la r´ ecurrence lin´ eaire
associ´ ee, sous les conditions initiales 001 g´ en` ere la suite {a
n } de p´ eriode 7 dans laquelle
la fenˆ etre suivante est r´ ep´ et´ ee :
0010111.
Le g´ en´ erateur combin´ e a donc comme p´ eriode 7 × 26 = 182. Nous pr´ esentons ses sorties
par blocs de trois lignes : la premi` ere ligne de chaque bloc repr´ esente une p´ eriode de la
premi` ere r´ ecurrence lin´ eaire. La deuxi` eme ligne repr´ esente la suite correspondante a
n :
des traits verticaux s´ eparent les diff´ erentes fenˆ etres r´ ep´ etant la p´ eriode. La troisi` eme
ligne repr´ esente les sorties
an
3 +
a
n
2 . Toutes ces sorties ont ´ et´ e ´ ecrites en multiples de
1
6 pour mettre en ´ evidence le fait que les num´ erateurs forment une suite de nombres
al´ eatoires de {0, 1, . . . , 5}. Ainsi, le premier bloc repr´ esente n = 0, . . . , 25, le second
n = 26, . . . , 51, etc.
On voit que, si les nombres p i sont petits, la r´ egularit´ e des sorties des diff´ erents
nombres ou sous-suites n’apparaˆ ıt pas aussi rapidement que dans les r´ ecurrences F p -
lin´ eaires.