XORShift random number generators

On this page, we describe the XORShift technique for generating medium-quality random numbers. Like other techniques, XORShift generates higher quality random numbers than the standard java.lang.Random class. It should be said that as a technique for generating random numbers in Java, it has been largely surpassed by the ThreadLocalRandom class since Java 8. However, the XORSfhit algorithm is worth knowing about as a general programming technique, not least because you will find it used in other Java source code— including the JDK!

XORShhift in Java

The XORShift technique was proposed by George Marsalia in 2003. It generates random numbers using a single seed and just 3 shifts and XOR operations. It can be used to generate different bit widths, with 32-bit and 64-bit versions being common. The 64-bit XORShift algorithm in Java looks as follows:

long seed = Systen.nanoTime();
	
public long randomLong() {
  seed ^= (seed << 21);
  seed ^= (seed >>> 35);
  seed ^= (seed << 4);
  return seed;
}

In this example, we use Systen.nanoTime() for the initial seed, but any source of entropy or "seed randomness" is possible in principle. As with other generators, we can also start with a known fixed seed if we always want to generate the same predetermined sequence, e.g. for replicability in unit tests or simulations.

What are the numbers 21, 35 and 4? In fact, different shift values are possible, and the direction of the shifts can also be reversed. But Marsaglia's mathematical proof shows that certain combinations of shifts such as (21, 35, 4) will generate a "full" period: the above example will cycle round all 2⁶⁴-1 possible non-zero long values. Marsaglia also found that the resulting values from certain shift values pass his "Diehard battery" of statistical tests for randomness¹. L'Ecuyer & Simard (2007)² also found that values of 13, 7 and 17 fail on only 7 of the 160 tests of their BigCrush battery (for comparison, java.util.Random fails on 21, while crypographic generators such as Java's SecureRandom— as indeed we might expect— generally pass all tests).

XORShift vs cryptographic RNGs and other techniques

Cryptographic quality random number generators and hashing algorithms also use very simple bitwise operations, such as XOR, addition, bit shifts and rotations³. So why not simply use SecureRandom, for example?

The advantage of XORShift and similar techniques is a performance/quality tradeoff: SecureRandom is typically tens if not hundreds of times slower than a simpler technique such as XORShift or ThreadLocalRandom, while still being of high enough quality for many applications.

Subclassing Random with an XORShift generator

As mentioned above, if you are looking for a fast but higher quality alternative to the Java Random class, then ThreadLocalRandom is probably the default choice since Java 8. That said, it is also possible to subclass java.lang.Random to use a different generation technique such as XORShift.

Problems and advantages with XORShift generators

The XORShift algorithm is a vast improvement on LCG generators. However, it does still have at least a couple of weaknesses. These weaknesses can be alleviated by combining XORShift with a secondary generator:

• used "raw", XORShift will never produce the value 0 (the value is clearly outlawed, or the generator would get stuck on zero!); used to produce long values as a sequence of calls, there'll always be one possible value that won't be produced;
• the generator will occasionally go through cycles in which few bits are set in the numbers generated;
• other techniques such as the algorithm used in ThreadLocalRandom produce better quality random numbers with better or comparable performance.

On the other hand, due to its simplicity, XORShift still has its place as a quick "inline" random number generation technique.

Not cryptographically secure

Needless to say, XORShift on its own is not cryptographically secure: it is relatively trivial for somebody observing a couple of numbers generated to deduce (at worst by trial and error) the shift values used, and hence predict future numbers.

Other random number generators in Java

The most common competitor to XORShift in Java is the ThreadLocalRandom class. The SplittableRandom class will also be appropriate in some more specialist circumstances.

1. The values used here are ones that the Numerical Recipes authors suggest "may be slightly superior" to other recommended values (3rd ed, p. 346).
2. L'Ecuyer, P. & Simard, R. (2007) TestU01: A C Library for Empirical Testing of Random Number Generators, ACM Transactions in Mathematical Software 33
3. In fact, they generally also use substitution: taking some partial value and using it as an index into an array of "random-looking" values in order to add additional unpredictability.