8.6 Exercices
265
3. Le g´ en´ erateur lin´ eaire congruentiel de l’exercice 2 g´ en` ere une suite de nombres
entiers uniform´ ement distribu´ es dans E = {1, . . . , p − 1}. Trouver une mani` ere de
transformer cette suite en une suite de 0 et de 1 de telle sorte que 0 et 1 soient
´ equiprobables.
4. L’exercice suivant est destin´ e ` a montrer qu’un g´ en´ erateur lin´ eaire congruentiel
comme celui de l’exercice 2 n’a pas toujours de bonnes propri´ et´ es statistiques. Prenons p = 151, la racine primitive a = 30 et la condition initiale x 0 = 1. Voici le
segment {x n }
150
n=1 de la suite :
30 145 122 36 23 86 13 88 73 76 15 148 61 18 87
43 82 44 112 38 83 74 106
9 119 97 41 22 56 19
117 37 53 80 135 124 96 11 28 85 134 94 102 40 143
62 48 81 14 118 67 47 51 20 147 31 24 116
7
59
109 99 101 10 149 91 12 58 79 105 130 125 126
5 150
121
6 29 115 128 65 138 63 78 75 136
3 90 133 64
108 69 107 39 113 68 77 45 142 32 54 110 129 95 132
34 114 98 71 16 27 55 140 123 66 17 57 49 111
8
89 103 70 137 33 84 104 100 131
4 120 127 35 144 92
42 52 50 141
2
60 139 93 72 46 21 26 25 146
1.
On le transforme en une suite de 0 et de 1 en posant
y n =
0, x n ≤ 75,
1, x n ≥ 76,
ce qui nous donne la suite :
0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0
1 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0
1 1 1 0 1 1 0 0 1 1 1 1 1 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0
1 0 1 0 1 0 1 0 1 0 0 1 1 1 1 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0
1 1 0 1 0 1 1 1 1 0 1 1 0 1 1 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0.
a) Quelles sont les fr´ equences respectives de 0 et de 1 ?
b) Quelles sont les fr´ equences respectives des diff´ erentes sous-suites de longueur
2 : 00, 01, 10, 11 ? Dans un bon g´ en´ erateur de nombres al´ eatoires, elles devraient
ˆ etre `
a peu pr` es ´ egales. Que pouvez-vous conclure ?
c) Mˆ eme question pour les sous-suites de longueur 3.
5. On consid` ere un registre `
a d´ ecalage (c’est-` a-dire un g´ en´ erateur F 2 -lin´ eaire) de
coefficients (q 0 , q 1 , q 2 , q 3 ) = (1, 0, 0, 1) et les conditions initiales (a 0 , a 1 , a 2 , a 3 ) =
(0, 0, 0, 1). V´ erifier que la suite g´ en´ er´ ee est p´ eriodique de p´ eriode 15, mais qu’elle
n’est pas celle de l’exemple 8.4.
265
3. Le g´ en´ erateur lin´ eaire congruentiel de l’exercice 2 g´ en` ere une suite de nombres
entiers uniform´ ement distribu´ es dans E = {1, . . . , p − 1}. Trouver une mani` ere de
transformer cette suite en une suite de 0 et de 1 de telle sorte que 0 et 1 soient
´ equiprobables.
4. L’exercice suivant est destin´ e ` a montrer qu’un g´ en´ erateur lin´ eaire congruentiel
comme celui de l’exercice 2 n’a pas toujours de bonnes propri´ et´ es statistiques. Prenons p = 151, la racine primitive a = 30 et la condition initiale x 0 = 1. Voici le
segment {x n }
150
n=1 de la suite :
30 145 122 36 23 86 13 88 73 76 15 148 61 18 87
43 82 44 112 38 83 74 106
9 119 97 41 22 56 19
117 37 53 80 135 124 96 11 28 85 134 94 102 40 143
62 48 81 14 118 67 47 51 20 147 31 24 116
7
59
109 99 101 10 149 91 12 58 79 105 130 125 126
5 150
121
6 29 115 128 65 138 63 78 75 136
3 90 133 64
108 69 107 39 113 68 77 45 142 32 54 110 129 95 132
34 114 98 71 16 27 55 140 123 66 17 57 49 111
8
89 103 70 137 33 84 104 100 131
4 120 127 35 144 92
42 52 50 141
2
60 139 93 72 46 21 26 25 146
1.
On le transforme en une suite de 0 et de 1 en posant
y n =
0, x n ≤ 75,
1, x n ≥ 76,
ce qui nous donne la suite :
0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0
1 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0
1 1 1 0 1 1 0 0 1 1 1 1 1 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0
1 0 1 0 1 0 1 0 1 0 0 1 1 1 1 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0
1 1 0 1 0 1 1 1 1 0 1 1 0 1 1 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0.
a) Quelles sont les fr´ equences respectives de 0 et de 1 ?
b) Quelles sont les fr´ equences respectives des diff´ erentes sous-suites de longueur
2 : 00, 01, 10, 11 ? Dans un bon g´ en´ erateur de nombres al´ eatoires, elles devraient
ˆ etre `
a peu pr` es ´ egales. Que pouvez-vous conclure ?
c) Mˆ eme question pour les sous-suites de longueur 3.
5. On consid` ere un registre `
a d´ ecalage (c’est-` a-dire un g´ en´ erateur F 2 -lin´ eaire) de
coefficients (q 0 , q 1 , q 2 , q 3 ) = (1, 0, 0, 1) et les conditions initiales (a 0 , a 1 , a 2 , a 3 ) =
(0, 0, 0, 1). V´ erifier que la suite g´ en´ er´ ee est p´ eriodique de p´ eriode 15, mais qu’elle
n’est pas celle de l’exemple 8.4.