4. 测试
XORWOW 生成器由 Marsaglia 提出 [5]，并已使用 TestU01 “Crush” 测试框架进行了测试 [6]。NIST 伪随机性测试的完整套件 [7] 也已运行，尽管重点一直是 TestU01。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 测试。例如，广受尊敬的梅森旋转算法 [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] 中概述的工作的改编。MTGP32 生成器在 “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] 中进行了描述。
使用 Pearson 卡方检验 [11]、 [12]、Jarque-Bera 检验 [13]、Kolmogorov-Smirnov 检验 [14]、 [15] 和 Anderson-Darling 检验 [16]，对每个生成器的正态分布进行了测试。
测试在 +/- 6 个标准差的范围内运行。运行了三个 Pearson 测试，单元格计数分别为 1000、100 和 25。测试输出的列标记为 PK（表示 1000 个单元格的 Pearson）、PC（表示 100 个单元格的 Pearson）、P25（表示 25 个单元格的 Pearson）、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
即使对数正态分布与正态分布密切相关，也已使用 Pearson 卡方检验和 Kolmogorov-Smirnov 检验对其进行了测试。
以下表格代表了 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
加扰 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
使用 Pearson 卡方检验 [11]，对每个生成器的泊松分布进行了测试。
测试在广泛的 lambda 值范围内运行，并将统计数据与使用 MKL 的泊松分布结果进行比较。