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.25

The 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.52

The 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.