- Period - How long a generator can run before it repeats the entire sequence.
- Uniformity - All the numbers within the range will appear.
- Predictability - how predictable is the next number in the sequence.
- Repeatability - can the same number repeat itself?
- Security - is the sequence invertable?
- Seekability - can we quickly skip over numbers?
- Streams - How usable is the generator when threading?
- k-dimensional equadistribution - How well distributed numbers are.
This diverse range of usage inevitably meant that there were a lot of different tests. L'Ecuyer and Simard made a huge contribution to testing in 2007 with the release of TestU01. They took a look at the myriad of tests that were available and created a test suite that includes a large number of previously independently published tests. They combined a number of different tests into batteries of tests (SmallCrush, BigCrush). Lots of the random number generators that were in common use at the time failed the test suite. The PCG paper covers testing of a large number of random number generators for those of you who are curious.
TestU01 is a C library with tests and generators for the most common PRNGs. This means that you need to write a simple C program to run the tests that you desire. Here is the version of Java's random number generator that I wrote to test it. Note that the values used are based on the API documentation and are the minimal random number generator that is required.
// Adapted from TestU01 manual, Figure 2.2, Figure 2.4
#include "TestU01.h"
// Example PRNG: Xorshift 32
static unsigned long x = 2463534242U;
static unsigned long a = 0x5DEECE66DL;
static unsigned long c = 11U;
unsigned int jvmlcg (void)
{
x = x * a + c;
return (int)(x>>16);
}
int main()
{
// Create TestU01 PRNG object for our generator
unif01_Gen* gen = unif01_CreateExternGenBits("JVM LCG", jvmlcg);
// Run the tests.
//bbattery_SmallCrush(gen);
bbattery_BigCrush(gen);
// Clean up.
unif01_DeleteExternGenBits(gen);
return 0;
}
The Java test did not do very well on the big crush test. I ran the tests in an emulator running Linux so that I didn't need to set up MinGW on my system as the libraries are for Unix. If you see a flaw in my program, feel free to email me. You can run the test for yourself but to save you hours of waiting, here are the final test results:
========= Summary results of BigCrush =========
Version: TestU01 1.2.3
Generator: JVM LCG
Number of statistics: 160
Total CPU time: 08:55:08.77
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
----------------------------------------------
2 SerialOver, r = 22 eps
4 CollisionOver, t = 2 1 - eps1
6 CollisionOver, t = 3 1 - eps1
8 CollisionOver, t = 7 eps
10 CollisionOver, t = 14 eps
12 CollisionOver, t = 21 eps
13 BirthdaySpacings, t = 2 eps
14 BirthdaySpacings, t = 3 eps
15 BirthdaySpacings, t = 4 eps
16 BirthdaySpacings, t = 7 eps
17 BirthdaySpacings, t = 7 eps
18 BirthdaySpacings, t = 8 eps
19 BirthdaySpacings, t = 8 eps
20 BirthdaySpacings, t = 16 eps
21 BirthdaySpacings, t = 16 eps
22 ClosePairs mNP, t = 3 1.6e-26
22 ClosePairs mNP1, t = 3 1.3e-48
22 ClosePairs mNP2S, t = 3 eps
23 ClosePairs mNP, t = 5 3.4e-4
23 ClosePairs mNP1, t = 5 3.4e-4
23 ClosePairs mNP2S, t = 5 eps
24 ClosePairs mNP2S, t = 9 5.7e-46
25 ClosePairs mNP, t = 16 8.0e-30
25 ClosePairs mNP1, t = 16 3.7e-29
25 ClosePairs mNP2S, t = 16 1.1e-283
27 SimpPoker, r = 27 eps
29 SimpPoker, r = 25 eps
32 CouponCollector, r = 20 eps
33 CouponCollector, r = 27 eps
35 Gap, r = 25 eps
37 Gap, r = 20 eps
43 Permutation, t = 10 0.9997
58 AppearanceSpacings, r = 27 eps
60 WeightDistrib, r = 20 eps
61 WeightDistrib, r = 28 eps
64 WeightDistrib, r = 26 eps
67 MatrixRank, L=30, r=26 7.9e-10
75 RandomWalk1 H (L=50, r=25) eps
75 RandomWalk1 M (L=50, r=25) eps
75 RandomWalk1 J (L=50, r=25) eps
75 RandomWalk1 R (L=50, r=25) eps
75 RandomWalk1 C (L=50, r=25) eps
85 Fourier3, r = 27 eps
87 LongestHeadRun, r = 27 eps
87 LongestHeadRun, r = 27 1 - eps1
89 PeriodsInStrings, r = 20 1 - eps1
91 HammingWeight2, r = 27 5.0e-13
96 HammingIndep, L=30, r=27 eps
98 HammingIndep, L=300, r=26 eps
100 HammingIndep, L=1200, r=25 eps
102 Run of bits, r = 27 eps
106 AutoCor, d=3, r=27 2.6e-7
----------------------------------------------
All other tests were passed
One interesting observation that Melissa made in her study is that the XORShift did poor in the crush tests but it's companion XORShift* did exceptionally well. This is a surprise when you consider that XORShift and XORSHift* use the same shift-and-apply-xor operations. The only difference between XORShift and XORShift* is XORShift* adds a multiplication at the end. Anybody familiar with random number generators will know that Linear Congruential Generators (LCGs) work by multiplying then adding. This means that XORShift* gains it's powers by essentially running it's output through a LCG.
If an improvement step works for XORShift, would such an improvement step work for a LCG?
No comments:
Post a Comment