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.