4. 测试
XORWOW生成器由Marsaglia提出[5]，并已通过TestU01测试框架中的"Crush"测试套件验证[6]。虽然重点放在TestU01上，但也运行了完整的NIST伪随机性测试套件[7]。TestU01测试集中最严格的是"BigCrush"，它在一台高端CPU/GPU上约5小时内执行106项统计测试。XORWOW生成器在大多数运行中能通过所有测试，但偶尔会产生可疑的统计结果。以下是一个未通过全部测试的运行示例摘要输出，包含具体失败细节。
========= 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 *****
为了更直观地理解这一点，[6]中有一个表格展示了在多种生成器上运行不同级别"Crush"测试的结果。只有少数生成器能通过所有BigCrush测试。例如广受推崇的Mersenne twister[8]就始终无法通过其中两项线性复杂度测试。
MRG32k3a生成器在[9]中被提出，并在[10]中给出了具体实现建议。该生成器能稳定通过所有"BigCrush"测试，偶尔会出现如下所示的边缘性结果。
========= 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
MTGP32生成器是基于[1]中所述工作的改进版本。该生成器在"BigCrush"测试中表现出部分边缘性结果。示例如下：
========= 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
MT19937生成器是目前为止使用最广泛的伪随机数生成器(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
Philox4_32_10生成器是[17]中描述的基于计数器的RNG之一。
========= 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序列是使用Joe和Kuo推荐的方向向量生成的[2]。加扰Sobol方法在[3]和[4]中有描述。
对每个生成器进行的正态分布测试，已使用皮尔逊卡方检验[11]、[12]，Jarque-Bera检验[13]，Kolmogorov-Smirnov检验[14]、[15]以及Anderson-Darling检验[16]完成。
测试在正负6个标准差的范围内进行。运行了三个皮尔逊检验，单元格计数分别为1000、100和25。测试输出列标签为：PK表示1000个单元格的皮尔逊检验，PC表示100个单元格的皮尔逊检验，P25表示25个单元格的皮尔逊检验，JB表示Jarque-Bera检验，KS表示Kolmogorov-Smirnov检验，AD表示Anderson-Darling检验。每个检验的拒绝标准打印在标签下方。
以下表格展示了XORWOW、MRG32k3a、MTGP32、MT19937、Philox、Sobol 32位以及加扰Sobol 32位生成器在正态分布统计测试中的代表性输出结果。每张表格的行表示基于连续10000个样本序列计算得出的统计结果。
XORWOW生成器：
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 生成器：
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生成器：
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生成器：
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 生成器：
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位生成器：
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
加扰Sobol 32位生成器：
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
尽管对数正态分布与正态分布密切相关，但它也通过了皮尔逊卡方检验和科尔莫戈罗夫-斯米尔诺夫检验的验证。
以下表格展示了针对XORWOW、MRG32k3a、MTGP32、MT19937、Philox、Sobol 32位以及加扰Sobol 32位生成器的对数正态分布统计测试的代表性输出结果。
XORWOW随机数生成器：
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生成器：
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生成器：
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生成器：
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 生成器：
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位生成器：
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位生成器:
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
对泊松分布的测试，使用每种生成器，均采用了皮尔逊卡方检验[11]。
测试在广泛的lambda值范围内运行，并将统计结果与使用MKL的泊松分布结果进行比较。