Saturday, January 5, 2019

Testing Random Number Generators

There are a number of factors that people look for in a random number generator.


  • 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?