Xorshift

Xorshift random number generators are a class of pseudorandom number generators that was discovered by George Marsaglia.^[1] They generate the next number in their sequence by repeatedly taking the exclusive or of a number with a bit shifted version of itself. This makes them extremely fast on modern computer architectures. They are a subclass of linear feedback shift registers, but their simple implementation typically makes them faster and use less space.^[2] However, the parameters have to be chosen very carefully in order to achieve a long period.^[3]

Xorshift generators are among the fastest non-cryptographic random number generators requiring minimal code and state. Although they do not pass every statistical test without further refinement, this weakness is well-known and easily amended (as pointed out by Marsaglia in the original paper) by combining them with a non-linear function, resulting e.g. in a xorshift+ or xorshift* generator. A naive C implementation of a xorshift+ generator that passes all tests from the BigCrush suite (with an order of magnitude fewer failures than Mersenne Twister or WELL) typically takes fewer than 10 clock cycles on x86 to generate a random number thanks to instruction pipelining.^[4]

Because plain xorshift generators (without a non-linear step) fail a few statistical tests, they have been accused of being unreliable^[3]:360 and not suitable for cryptographic purposes. However, considering the previous paragraph, it is debatable whether or not this is a fair objection.

Example implementation

A C/C++ version^{[note 1]} of one xorshift algorithm ^[1] is:

#include <stdint.h>
 
/* These state variables must be initialized so that they are not all zero. */
uint32_t x, y, z, w;
 
uint32_t xorshift128(void) {
    uint32_t t = x ^ (x << 11);
    x = y; y = z; z = w;
    return w = w ^ (w >> 19) ^ t ^ (t >> 8);
}

This algorithm has a maximal period of 2¹²⁸ − 1^[3] and passes the diehard tests. However, it fails the MatrixRank and LinearComp tests of the BigCrush test suite from the TestU01 framework.

Variations

All xorshift generators fail some tests out of TestU01's BigCrush test suite. This is true of all generators based on linear recurrences, such as the Mersenne Twister or WELL. However, it is easy to scramble the output of such generators to improve their quality.

Xorshift*

A xorshift* generator takes an xorshift generator, and performs an invertible multiplication (modulo the word size) to its output as a non-linear transformation, as suggested by Marsaglia.^[1] The following 64-bit generator with 64 bits of state has a maximal period of 2⁶⁴ − 1^[5] and fails only the MatrixRank test of BigCrush:

#include <stdint.h>
#define UINT64_C(val) (val##ULL)
 
uint64_t x; /* The state must be seeded with a nonzero value. */
 
uint64_t xorshift64star(void) {
	x ^= x >> 12; // a
	x ^= x << 25; // b
	x ^= x >> 27; // c
	return x * UINT64_C(2685821657736338717);
}

A similar generator is suggested in Numerical Recipes,^[6] but it fails also the BirthdaySpacings test.

The following generator has 1024 bits of state, a maximal period of 2¹⁰²⁴ − 1,^[5] and passes BigCrush:

#include <stdint.h>
#define UINT64_C(val) (val##ULL)
 
/* The state must be seeded so that it is not everywhere zero. If you have
   a 64-bit seed,  we suggest to seed a xorshift64* generator and use its
   output to fill s. */
 
uint64_t s[16];
int p;
 
uint64_t xorshift1024star(void) {
	uint64_t s0 = s[ p ];
	uint64_t s1 = s[ p = (p+1) & 15 ];
	s1 ^= s1 << 31; // a
	s1 ^= s1 >> 11; // b
	s0 ^= s0 >> 30; // c
	return ( s[p] = s0 ^ s1 ) * UINT64_C(1181783497276652981);
}

Both generators, as with all xorshift* generators of maximal period, emit a sequence of 64-bit values that is equidistributed in the maximum possible dimension.^[5]

Xorshift+

Rather than using multiplication, it is possible to use addition as a faster non-linear transformation. First proposed by Saito and Matsumoto (also responsible for the Mersenne twister), their XSadd generator sums two consecutive outputs of an underlying xorshift generator.^[7]

XSadd, however, fails several BigCrush tests when bit-reversed. The following xorshift+ generator uses 128 bits of state and has a maximal period of 2¹²⁸ − 1.^[8] It passes BigCrush.

#include <stdint.h>
 
/* The state must be seeded so that it is not everywhere zero. */
uint64_t s[2];
 
uint64_t xorshift128plus(void) {
	uint64_t x = s[0];
	uint64_t const y = s[1];
	s[0] = y;
	x ^= x << 23; // a
	x ^= x >> 17; // b
	x ^= y ^ (y >> 26); // c
	s[1] = x;
	return x + y;
}

This generator is one of the fastest generators passing BigCrush.^[4] One disadvantage of this construct is that, while two words of state produce a 2-dimensionally equidistributed xorshift generator, adding adjacent outputs reduces this to 1-dimensionally equidistributed.^[8]

Notes

References