Building PCG

A LCG basically uses the following calculation: X[n] = (A * X[n-1] + C) % M. X[n] is the next number in the sequence to generate with A being a specially selected multiplier value, C is a value to add to the generator, and M is the modulus or range of the generator. We will use Rotenberg's values of 141 for A, 3 for C and just use a byte so 256 for the modulus. Lets generate a randogram and see what we get.

While this is not as good as we hoped, it is not as bad as it seems as the order the dots appear is random. We are using an 8 bit generator so what if we went with 16? Obviously the lower order byte would remain the same but what if we took higher bits for the output.

Interesting enough, each bit you shift becomes more random with different shifts having different coverage of the randogram. What if we added a permutation to select from some of the better shifts? If only we had a random way of selecting which shift to use. What about the top 2 bits (more for larger generators)? While they have the most randomness, we may gain overall.

Melissa added additional permutations for rotation, XOR, and XORShift. More permutations are possible if you follow the rules:

• Bits can be thrown away but you can't make new ones (precious).
• Target and control groups of bits must be separate.
• Control bits must not be modified.
• Can do many rounds and different rounds can have different control bits.

By combining different permutations, it was possible to complete BigCrush using only a 36 bit PCG (Permuted Congruential Generators). So, in conclusion PCG is a family of Pseudo-Random Number Generation algorithms. They are relatively simple to implement. They run Fast as the code is simple boolean operations, multiplications and additions. They are Space-Efficient requiring less than double the modulus size. And passing the TestU01 BigCrush tests shows they are Statistically Good.

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?