- 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