On
génère N entiers de la suite (Xn) dans l’intervalle [1,r].
Grossièrement, Si la répartition est homogène (cas idéal), chaque entier de [1,r]
est généré N/r fois.
On met donc en évidence la différence entre le nombre d’occurrences observé fi
de chaque entier i et N/r, divisée par N/r (pour tenir compte de l'importance
de chaque terme quand leur probabilité d'apparitions diffèrent) par une mise
au carré :
|
|
p = 1%
|
p = 5%
|
p = 25%
|
p = 50%
|
p = 75%
|
p = 95%
|
p = 99%
|
|
v = 1
|
0.00016
|
0.00393
|
0.1015
|
0.4549
|
1.323
|
3.841
|
6.635
|
|
v = 2
|
0.02010
|
0.1026
|
0.5753
|
1.386
|
2.773
|
5.991
|
9.210
|
|
v = 3
|
0.1148
|
0.3518
|
1.213
|
2.366
|
4.108
|
7.815
|
11.34
|
|
v = 4
|
0.2671
|
0.7107
|
1.923
|
3.357
|
5.385
|
9.488
|
13.28
|
|
v = 5
|
0.5543
|
1.1455
|
2.675
|
4.351
|
6.626
|
11.07
|
15.09
|
|
v = 6
|
0.8720
|
1.635
|
3.455
|
5.348
|
7.841
|
12.59
|
16.81
|
|
v = 7
|
1.239
|
2.167
|
4.255
|
6.346
|
9.037
|
14.07
|
18.48
|
|
v = 8
|
1.646
|
2.733
|
5.071
|
7.344
|
10.22
|
15.51
|
20.09
|
|
v = 9
|
2.088
|
3.325
|
5.899
|
8.343
|
11.39
|
16.92
|
21.67
|
|
v = 10
|
2.558
|
3.940
|
6.737
|
9.342
|
12.55
|
18.31
|
23.21
|
|
v = 11
|
3.053
|
4.575
|
7.584
|
10.34
|
13.70
|
19.68
|
24.73
|
|
v = 12
|
3.571
|
5.226
|
8.438
|
11.34
|
14.84
|
21.03
|
26.22
|
|
v = 15
|
5.229
|
7.261
|
11.04
|
14.34
|
18.25
|
25.00
|
30.58
|
|
v = 20
|
8.260
|
10.85
|
15.45
|
19.34
|
23.83
|
31.41
|
37.57
|
|
v = 30
|
14.95
|
18.49
|
24.48
|
29.34
|
34.80
|
43.77
|
50.89
|
|
v = 50
|
29.71
|
34.76
|
42.94
|
49.33
|
56.33
|
67.50
|
76.15
|
|
v >
30
|
 |
||||||
|
xp =
|
-2.33
|
-1.64
|
-0.675
|
0.00
|
0.675
|
1.64
|
2.33
|
Pour plus de valeurs, se reporter au Handbook of Mathematical Functions, ed. pas M. Abramowitz & I. A Stegun ( Washington, DC: US Government Printing Office, 1964 ), Table 26.8. ).
Elle indique que, par exemple, pour 30 degrés de liberté, la somme précédemment mentionnée est inférieure à 43,77 95% du temps, et infèrieure à 24,48 25% du temps.
On va tester 3 types d'algorithmes:
- le générateur basé sur la suite de terme général, Xn = (427419669081 Xn-1) mod (1012 - 11) qui revoie un entier inférieur strict à l’argument reçu:
random_Maple(1234567);
981953
- le registre à décalage à rétroaction linéaire utilisé dans le logiciel Caml
- le générateur utilisé par le langage C ( ici à l'aide de Visual C++ )
initialisé par: srand ( time ( NULL ) ) ;
et appelé par rand () % max ;
Procédures de test:
- Pour chaque algorithme, on génère 6 000 entiers compris entre 1 et 300 (inclus). On effectue un test du chi2 sur les 6 000 valeurs générées.
chi2(random_Maple,6000,300,10);
30.46
- On va donc répéter l'opération un grand nombre de fois (en l'occurrence 4 000), et obtenir à chaque fois une valeur caractéristique.
- Ensuite, on trie dans l'ordre croissant les 4 000 valeurs obtenues (l'ordre d'apparition n'ayant aucune importance dans le test en cours), et on représente le graph (où y valeur de l'occurrence est fonction de x numéro d'occurrence) pour les 3 générateurs étudiés.
Interprétation des Résultats:
Les résultats semblent assez proches au premier abord. Néanmoins les générateurs sont loin d'être de qualité équivalente!
En effet, c'est quand on observe le démarrage des courbes (zoom), que l'on remarque les différences les plus flagrantes. Il y a notamment beaucoup moins de points pour le générateur du C que souhaités. Cela se confirme par l'étude de la liste des 4 000 valeurs obtenues pour chaque générateur.
C'est effectivement au départ des courbes que les générateurs sont les plus mis en défaut: les écarts sont énormes (respectivement 25, 42.5, et 25% dans la première colonne). Cela signifie qu'en théorie, on devrait observer plus de valeurs engendrant des chi2 faibles. Les chi2 faibles sont obtenus pour une répartition telle que les valeurs apparaissent toutes en nombre identique. Cela n'est pas le cas pour ces générateurs, et ceci est encore plus vrai pour le générateur du C.
Un petit utilitaire RandTest, est en cours de développement. Il doit permettre d'automatiser les tests sur différents générateurs. Il est actuellement dans sa version beta 1: il est capable de tester le générateur du C, ainsi que le générateur linéaire congruentiel et le LFSR précédemment décrits.
À court terme il sera capable de tester d'autres générateurs, et à moyen terme d'effectuer d'autres tests que ceux du chi2! (les sources seront disponibles prochainement).
voici une copie d'écran:
Pour le télécharger dans sa version beta 1 (exécutable Windows zippé: 62 ko) : RandTest_beta_0.1.zip
Le chi2 a été précédemment appliqué afin de déterminer si les éléments étaient uniformément distribués, il s'agit de l'Equidistribution Test (ou Frequency Test).
Le Serial Test détermine si les paires d'entiers successifs sont distribuées uniformément et indépendamment; pour cela on effectue un test du chi2 sur les couples au lieu des entiers pris indépendamment.
Le Gap Test examine la longueur des intervalles (gaps) entre deux occurrences du même entier.
Il y a beaucoup d'autres tests comme le Poker Test (ou Partition Test), le Coupon Collector's Test, le Permutation Test, le Run Test, le Maximum-of-t Test, le Collision Test, le Serial Correlation Test... voir The Art of Computer Programming Vol. 2 pour plus d'informations.