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
7 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.
An Advent calendar is a special calendar used to count or celebrate the days in anticipation of Christmas. Advent calendars typically begin on December 1 and provide a window to open until December 24. Usually they have windows, which you can open each day containing some chocolate or other stuff. But what is better to kill some time until Christmas, Hanukkah, Yule, Kwanzaa, Diwali, Boxing Day, etc. than an Advent calendar giving you a programming problem every day?
