Random Numbers in Java: Comparison of java.util.random, Xorshift, and PCG

In a previous post, we have shown how to replace the Java random number generator with a faster Xorshift algorithm, which also has nicer properties than the Java random number generator which was implemented in 1995.

Melissa E. O’Neill from Harvey Mudd College suggests a new class of random number generators called PCG. For a detailed description, see her paper "PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation".

Like the Xorshift algorithm, PCG is using a couple of shift and bitwise logical operators to generate random integers. Typically this is faster that Java's linear congruential generator. We have implemented a simple version of the PCG algorithm in order to compare its performance to java.util.random and our Xorshift implementation.

The best way to replace the Java random generator in our opinion is to make a subclass of java.util.random and to overwrite the next() method. For Xorshift, the algorithm is as follows:

import java.util.Random;

/**
 * A subclass of java.util.random that implements the 
 * Xorshift random number generator
 */

public class XSRandom extends Random {
 private long seed;

 public XSRandom(long seed) {
  this.seed = seed;
 }

 protected int next(int nbits) {
  long x = seed;
  x ^= (x << 21);
  x ^= (x >>> 35);
  x ^= (x << 4);
  seed = x;
  x &= ((1L << nbits) - 1);
  return (int) x;
 }
}

We implemented the PCG algorithm in Java based on the minimal C code example by M.E. O'Neill at pcg-random.org:

import java.util.Random;

/**
 * A subclass of java.util.random that implements the 
 * PCG32 random number generator
 * Based on the minimal code example by M.E. O'Neill / pcg-random.org
 * Licensed under Apache License 2.0
 */

public class PCGRandom extends Random {
 private long inc;
 private long state;
 
 public PCGRandom(long seed) {
  this.state = seed;
  inc=1;
 }

 public PCGRandom(long seed, long initseq) {
  // initseq selects the output sequence for the RNG
  this.state = seed;
  this.inc=initseq;
 }

 protected int next(int nbits) {
  long oldstate=state;
  // Advance internal state
  state=oldstate * 6364136223846793005L + (inc | 1);
  // Calculate output function (XSH RR), uses old state for max ILP
  long xorshifted = ((oldstate >> 18) ^ oldstate) >> 27;
  long rot = oldstate >> 59;
  return (int) ((xorshifted >> rot) | (xorshifted << ((-rot) & 31)));
 }
}

To use the class in legacy code, you may also instantiate an XSRandom object and assign it to a java.util.Random variable:

  java.util.Random rand = new XSRandom(); // or new PCGRandom

All method calls to rand are then using the new implementation.

The PCG algorithm comes with better properties regarding its period. But what about the performance?
We tested the performance by calculating 10⁷ random numbers subsequently, repeating this 10 times with different starting seeds. Then we compared the average execution time for a program compiled under Java 8 running single threaded on an core i7 notebook computer. Results show that for our implementation, the PCG algorithm has a very similar execution time to the original Java random generator, while the Xorshift is significantly faster.

Execution time of java.util.random, Xorshift, and PCG. Please note that y axis starts at 10 ns.

So if you mainly care about speed, go for Xorshift. If statistical quality is important, go for PCG. If you want a bad random number generator and have a lot of time, stick with java.util.random.

Replacing the Java random generator

The Java random number generator was implemented in 1995. It is based on a linear congruential generator. Since then, there was considerable advancement in algorithms for pseudo random number generators. For most applications, Java's random number generator might be sufficient, but at a closer look, the algorithm has a fairly short period of 2⁴⁸ and fails some tests on the randomness of its output.
The good news is that there is an algorithm which is faster and better: the Xorshift algorithm. Xorshift is using a few (in the following implementation exactly three) of shift and exclusive-or operations. The best way to integrate it to Java is to make a subclass of java.util.random and to overwrite the seed variable and the next() method:

import java.util.Random;

/**
 * A subclass of java.util.random that implements the 
 * Xorshift random number generator
 */

public class XSRandom extends Random {
 private long seed;

 public XSRandom(long seed) {
  this.seed = seed;
 }

 protected int next(int nbits) {
  long x = seed;
  x ^= (x << 21);
  x ^= (x >>> 35);
  x ^= (x << 4);
  seed = x;
  x &= ((1L << nbits) - 1);
  return (int) x;
 }
}

Since all methods of the Random generator (nextBoolean(), nextInt(), nextLong(), nextFloat(), nextDouble()), nextBytes(), nextGaussian()) depend on the next() method, this efficiently changes all number generation to the Xorshift algorithm.
A complete Java class including also a clone() method can be downloaded here (Code is under LGPL Version 3). Note that this implementation, unlike the java.util.Random is not exactly thread-safe - concurrent threads might access and change the seed variable inconsistently. However, note that concurrent access on the same random object would anyway end up in a nondeterminstic sequence of numbers for each thread.
This implementation is about 30% faster than the generator from java.util.random. It's output passes the Dieharder test suite with no fail and only two announced weaknesses. To use the class in legacy code, you may also instantiate an XSRandom object and assign it to a java.util.Random variable:

  java.util.Random rand = new XSRandom();

All method calls to rand are then using the newer, faster implementation.

Pseudo random number generators

In the previous post, we learned that a complex system can exhibit deterministic, but unpredictable behavior. Actually, this aspect has a strong application in computers that has been around for a long time: random number generators.
Many computer programs, like for example games or Monte Carlo simulation require a random function. Typically, a computer operating on defined binary states that only change at particular clock instants has no true randomness - its operations are deterministic. So, typically pseudo random number generators are used to generate number sequences similar to random ones.
In 1946, John von Neumann suggested such an algorithm named the middle-square method. Von Neumann's algorithm is simple: take a number as the "seed", square it, remove the middle digits of the resulting number (when viewed in decimal format) and take the remaining digits as your "random number". This number becomes also the new seed. The algorithm is fast, but statistic tests on the generated random numbers show that the distribution of numbers significantly differs from true random numbers. Worse, once the seed becomes zero, the algorithm gets stuck.
A few decades after Neumann, the programming language C came with a library function for generating random numbers using the functions rand (to pull a number) and srand (to set the seed). For generating one number, the algorithm linearly combines several terms based on constants derived from the seed. This means a higher implementation effort, but the test passes most statistical tests on randomness, such as for example are given ba the Dieharder random test suite.
The famous home computer Commodore 64 had a different algorithm for random number generation, which was simpler: The last seed is multiplied with a big number, a small number is added and the resulting number (given in a floating point format) is mixed up by switching bytes. Although the C64 algorithm was considered practically useful in a publication from Bowman, the Diehard test quickly shows a lot of deficiencies of the algorithm.
In 1997, Makoto Matsumoto and Takuji Nishimura came up with a very good algorithm, the Mersenne Twister. While this algorithm passes most of the Dieharder tests, the implementation has also grown in its complexity. For example, a common implementation of the algorithm requires an array of 624 numbers.

So - do you think now there is a tradeoff between quality of randomness and computation effort? Wrong!

The late (and great) George Marsaglia showed us a simple way to generate high quality numbers: the Xorshift algorithm.

public long randomLong() {
  x ^= (x << 21);
  x ^= (x >>> 35);
  x ^= (x << 4);
  return x;
}

The computational effort of the algorithm is obviously very low. If you chose "good" values for the three magic numbers (e.g., 21, 35, 4 as in the above example) Xorshift passes the Diehard tests. As it is the case in many complex systems, there is a simple way to control the systems behavior as intended, but is very difficult to find that simple way. In the case of pseudo random numbers it took 60 years from John von Neumann's middle-square to George Marsaglia's Xorshift.

• J. von Neumann. "Various techniques used in connection with random digits", in A.S. Householder, G.E. Forsythe, and H.H. Germond, eds., Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, 12:36-38, reprinted 1951.
  
• M. Matsumoto and T. Nishimura. "Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator". ACM Transactions on Modeling and Computer Simulation 8(1):3–30, 1998
  
• R. Bowman. Evaluating Pseudo-Random Number Generators. Comput. &amb; Graphics, Vol. 19, No. 2, pp. 315-324, 1995.
  
• G. Marsaglia. "Xorshift RNGs". Journal of Statistical Software Vol. 8 No. 14, 2003.