4. Testing
The XORWOW generator was proposed by Marsaglia [5] and has been tested using the TestU01 "Crush" framework of tests [6]. The full suite of NIST pseudorandomness tests [7] has also been run, though the focus has been on TestU01. The most rigorous the the TestU01 batteries is "BigCrush", which executes 106 statistical tests over the course of approximately 5 hours on a high-end CPU/GPU. The XORWOW generator passes all of the tests on most runs, but does produce occasional suspect statistics. Below is an example of the summary output from a run that did not pass all tests, with the detail of the specific failure.
========= Summary results of BigCrush =========
Version: TestU01 1.2.3
Generator: curandXORWOW
Number of statistics: 160
Total CPU time: 05:17:59.63
The following tests gave p-values outside [0.001, 0.9990]:
(eps means a value < 1.0e-300):
(eps1 means a value < 1.0e-15):
Test p-value
----------------------------------------------
81 LinearComp, r = 29 1 - 7.1e-11
----------------------------------------------
All other tests were passed
Detail from test 81:
scomp_LinearComp test:
-----------------------------------------------
N = 1, n = 400020, r = 29, s = 1
-----------------------------------------------
Number of degrees of freedom : 12
Chi2 statistic for size of jumps : 7.11
p-value of test : 0.85
-----------------------------------------------
Normal statistic for number of jumps : -6.41
p-value of test : 1 - 7.1e-11 *****To put this into perspective, there is a table in [6] that gives the results of running various levels of the "Crush" tests on a broad selection of generators. Only a small number of generators pass all of the BigCrush tests. For example the widely-respected Mersenne twister [8] consistently fails two of the linear complexity tests.
The MRG32k3a generator was proposed in [9], with a specific implementation suggested in [10]. This generator passes all "BigCrush" tests frequently, with occasional marginal results similar to those shown below.
========= Summary results of BigCrush =========
Version: TestU01 1.2.3
Generator: curandMRG32k3a
Number of statistics: 160
Total CPU time: 07:14:55.41
The following tests gave p-values outside [0.001, 0.9990]:
(eps means a value < 1.0e-300):
(eps1 means a value < 1.0e-15):
Test p-value
----------------------------------------------
59 WeightDistrib, r = 0 5.2e-4
----------------------------------------------
All other tests were passed
Detail from test 59:
svaria_WeightDistrib test:
-----------------------------------------------
N = 1, n = 20000000, r = 0, k = 256, Alpha = 0, Beta = 0.25
-----------------------------------------------
Number of degrees of freedom : 67
Chi-square statistic : 111.55
p-value of test : 5.2e-4 *****
-----------------------------------------------
CPU time used : 00:02:56.25The MTGP32 generator is an adaptation of the work outlined in [1]. The MTGP32 generator exhibits some marginal results on "BigCrush". Below is an example.
========= Summary results of BigCrush =========
Version: TestU01 1.2.3
Generator: curandMtgp32Int
Number of statistics: 160
Total CPU time: 05:45:29.49
The following tests gave p-values outside [0.001, 0.9990]:
(eps means a value < 1.0e-300):
(eps1 means a value < 1.0e-15):
Test p-value
----------------------------------------------
12 CollisionOver, t = 21 0.9993
----------------------------------------------
All other tests were passed
Detail from test 12:
smultin_MultinomialOver test:
-----------------------------------------------
N = 30, n = 20000000, r = 28, d = 4, t = 21,
Sparse = TRUE
GenerCell = smultin_GenerCellSerial
Number of cells = d^t = 4398046511104
Expected number per cell = 1 / 219902.33
EColl = n^2 / (2k) = 45.47473509
Hashing = TRUE
Collision test
CollisionOver: density = n / k = 1 / 219902.33
Expected number of collisions = Mu = 45.47
-----------------------------------------------
Results of CollisionOver test:
POISSON approximation :
Expected number of collisions = N*Mu : 1364.24
Observed number of collisions : 1248
p-value of test : 0.9993 *****
-----------------------------
Total number of cells containing j balls
j = 0 : 131940795334368
j = 1 : 599997504
j = 2 : 1248
j = 3 : 0
j = 4 : 0
j = 5 : 0
-----------------------------------------------
CPU time used : 00:04:32.52The MT19937 generator is, by far, the most widely used PRNG
========= Summary results of BigCrush ========= Version: TestU01 1.2.3 Generator: curandMT19937Int Number of statistics: 160 Total CPU time: 03:12:59.34 All tests were passed
The Philox4_32_10 generator is one of the counter-based RNGs described in [17].
========= Summary results of BigCrush ========= Version: TestU01 1.2.3 Generator: curandPHILOXInt Number of statistics: 160 Total CPU time: 03:18:50.30 All tests were passed
Sobol’ sequences are generated using the direction vectors recommended by Joe and Kuo [2]. The scrambled Sobol’ method is described in [3] and [4].
Testing of the normal distribution, with the each of the generators, has been done using the Pearson chi-squared test [11], [12], the Jarque-Bera test [13], the Kolmogorov-Smirnov test [14], [15], and the Anderson-Darling test [16].
Tests are run over the range +/- 6 standard deviations. Three Pearson tests are run, with cell counts 1000, 100, and 25. The test output has columns labeled PK for Pearson with 1000 cells, PC for Pearson with 100 cells, P25 for Pearson with 25 cells, JB for Jarque-Bera, KS for Kolmogorov-Smirnov, and AD for Anderson-Darling. The rejection criterion for each test is printed below the label.
The following tables are representative of the test output for statistical testing of the normal distribution for XORWOW, MRG32k3a, MTGP32, MT19937, Philox, Sobol’ 32-bit, and scrambled Sobol’ 32-bit generators. The rows of each table represent the statistical results computed over successive sequences of 10000 samples.
XORWOW Generator:
PK PC P25 JB KS AD
<1058 <118 <33 <4.6 <0.0122 <.632
----------------------------------------------------------------------------
684.48120 58.97784 20.44693 2.84152 0.00540 0.32829
686.37925 54.84938 7.79583 0.55109 0.00900 0.25832
673.21437 69.15825 15.46540 0.30335 0.00872 0.26772
568.26999 49.99519 8.85046 0.66624 0.00870 0.22939
639.10690 84.23040 10.19753 0.19844 0.00542 0.27939 MRg32k3a Generator:
PK PC P25 JB KS AD
<1058 <118 <33 <4.6 <0.0122 <.632
----------------------------------------------------------------------------
764.38500 74.48157 19.32716 1.50118 0.01103 0.60351
795.31006 74.15086 11.78414 1.15159 0.00821 0.35343
741.85426 91.88692 20.67103 2.34232 0.00900 0.61787
644.62093 70.68369 17.18277 0.32870 0.01243* 0.34630
806.02693 93.50691 23.10548 2.67340 0.00978 0.51466 MTGP32 Generator:
PK PC P25 JB KS AD
<1058 <118 <33 <4.6 <0.0122 <.632
----------------------------------------------------------------------------
924.62604 110.19868 23.45811 0.86919 0.00519 0.33411
708.76047 79.42919 20.67913 1.13427 0.01142 0.54632
674.17713 65.80415 13.09834 1.07799 0.01040 0.23860
733.35915 57.13829 17.66337 3.17017 0.01188 0.30864
620.17297 50.39043 14.75682 0.57970 0.00845 0.28916 MT19937 Generator:
PK PC P25 JB KS AD
<1058 <118 <33 <4.6 <0.0077 <.632
----------------------------------------------------------------------------
663.51515 67.53027 9.70908 0.70428 0.00482 0.22643
758.11526 65.27417 10.81213 0.16740 0.00541 0.24615
678.79743 60.92754 27.50102 1.33330 0.00546 0.42693
741.21087 82.42319 24.10450 1.84422 0.00570 0.41724
644.92464 71.74918 18.32281 1.01582 0.00546 0.30622 Philox_4x32_10 Generator:
PK PC P25 JB KS AD
<1058 <118 <33 <4.6 <0.0122 <.632
----------------------------------------------------------------------------
688.73231 78.60241 18.28300 0.23786 0.00520 0.24052
600.66650 59.78966 21.59090 4.24401 0.00464 0.49806
916.60146 78.16294 10.01345 1.53526 0.00660 0.25025
713.67544 61.20329 15.82239 0.79568 0.00614 0.26091
699.84498 80.73224 16.07304 1.37786 0.00464 0.29227 Sobol’ 32-bit generator:
PK PC P25 JB KS AD
<1058 <118 <33 <4.6 <0.0122 <.632
----------------------------------------------------------------------------
157.04578 6.47398 1.45802 0.19007 0.00024 0.00188
243.82767 11.98164 1.34982 0.00668 0.00030 0.00086
229.87234 10.40206 2.73912 0.04165 0.00036 0.00137
290.29451 17.09013 3.25717 0.02583 0.00042 0.00172
327.32072 19.22832 5.09510 0.00335 0.00036 0.00127 Scrambled Sobol’ 32-bit generator:
PK PC P25 JB KS AD
<1058 <118 <33 <4.6 <0.0122 <.632
----------------------------------------------------------------------------
255.80606 10.93180 1.33766 0.01226 0.00036 0.00112
258.84244 8.45589 1.56766 0.04164 0.00036 0.00170
585.34346 49.33610 5.32037 0.04069 0.00043 0.00208
337.50312 27.64720 3.38925 0.01953 0.00041 0.00211
729.56687 56.89682 32.89772 0.00911 0.00040 0.00204 Even though the log-normal distribution is closely derived from the normal distribution, it has also been tested using the Pearson chi-squared test and the Kolmogorov-Smirnov test.
The following tables are representative of the test output for statistical testing of the log normal distribution for XORWOW, MRG32k3a, MTGP32, MT19937, Philox, Sobol’ 32-bit, and scrambled Sobol’ 32-bit generators.
XORWOW generator:
PK PC P25 KS
<1058 <118 <33 <0.0122
----------------------------------------------------
1019.57936 105.63667 13.15820 0.00540
991.93663 91.95369 20.46549 0.00900
983.09678 115.34978 20.50434 0.00872
966.45604 113.30013 24.54060 0.00870
996.35262 111.50026 21.01332 0.00542 MRG32k3a generator:
PK PC P25 KS
<1058 <118 <33 <0.0122
----------------------------------------------------
1000.00359 90.12428 22.82709 0.00826
942.17843 81.16259 16.13670 0.00739
1005.62148 102.29924 23.62705 0.00697
1053.68391 98.75565 28.65422 0.01107
998.38936 103.43649 19.26568 0.00803 MTGP32 generator:
PK PC P25 KS
<1058 <118 <33 <0.0122
----------------------------------------------------
1010.18903 94.51850 17.98126 0.00771
993.78319 76.86543 12.48859 0.00831
1010.22068 63.76027 11.65743 0.00677
963.33103 89.44369 17.96636 0.01200
927.15616 75.85515 13.64221 0.00566 MT19937 generator:
PK PC P25 KS
<1058 <118 <33 <0.0122
----------------------------------------------------
929.15309 83.63208 16.91037 0.00482
1058.79511 114.19971 27.28300 0.00541
963.35338 103.52657 26.68634 0.00546
1009.21512 114.36706 38.44470 0.00570
976.91303 84.83272 14.78584 0.00546 Philox_4x32_10 generator:
PK PC P25 KS
<1058 <118 <33 <0.0122
----------------------------------------------------
992.19843 100.39826 14.91235 0.00357
962.03714 115.40663 18.03086 0.00595
1006.41781 92.84903 27.33686 0.00385
1009.75491 96.93654 11.99484 0.00520
1003.85449 89.00801 15.64060 0.00464 Sobol’ 32-bit generator:
PK PC P25 KS
<1058 <118 <33 <0.0122
----------------------------------------------------
289.42589 5.03327 0.48858 0.00024
386.79860 6.57783 0.76902 0.00030
355.04631 8.54472 1.12228 0.00036
434.19211 9.54021 2.07006 0.00042
343.57507 10.71571 0.42503 0.00036 Scrambled Sobol- 32-bit generator:
PK PC P25 KS
<1058 <118 <33 <0.0122
----------------------------------------------------
354.55037 8.20727 0.24592 0.00036
506.45280 12.93848 0.73323 0.00036
451.96949 18.18903 0.69465 0.00043
593.25666 16.55782 0.54769 0.00041
423.05263 12.06600 0.53472 0.00040 Testing of the Poisson-distribution, with the each of the generators, has been done using the Pearson chi-squared test [11].
Tests are run over a broad range of lambda values, and the statistics are compared to those for Poisson distribution results using MKL.