Xorshift

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

Xorshift random number generators are a class of pseudorandom number generators that were discovered by George Marsaglia.[1] They are a subset of linear-feedback shift registers (LFSRs) which allow a particularly efficient implementation without using excessively sparse polynomials.[2] 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. Like all LFSRs, the parameters have to be chosen very carefully in order to achieve a long period.[3]

Xorshift generators are among the fastest non-cryptographically-secure random number generators, requiring very small 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 naïve 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

Example implementation[edit]

A C version[note 1] of three xorshift algorithms[1]:4,5 are given here. The first has one 32-bit word of state, and period 232−1. The second has one 64-bit word of state and period 264−1. The last has four 32-bit words of state, and period 2128−1. All use three shifts and three or four exclusive-or operations:

#include <stdint.h>

/* The state word must be initialized to non-zero */
uint32_t xorshift32(uint32_t state[static 1])
{
	/* Algorithm "xor" from p. 4 of Marsaglia, "Xorshift RNGs" */
	uint32_t x = state[0];
	x ^= x << 13;
	x ^= x >> 17;
	x ^= x << 5;
	return state[0] = x;
}

uint64_t xorshift64(uint64_t state[static 1])
{
	uint64_t x = state[0];
	x ^= x << 13;
	x ^= x >> 7;
	x ^= x << 17;
	return state[0] = x;
}

/* The state array must be initialized to not be all zero */
uint32_t xorshift128(uint32_t state[static 4])
{
	/* Algorithm "xor128" from p. 5 of Marsaglia, "Xorshift RNGs" */
	uint32_t s, t = state[3];
	state[3] = state[2];
	state[2] = state[1];
	state[1] = s = state[0];
	t ^= t << 11;
	t ^= t >> 8;
	return state[0] = t ^ s ^ (s >> 19);
}

The 128-bit algorithm passes the diehard tests. However, it fails the MatrixRank and LinearComp tests of the BigCrush test suite from the TestU01 framework.

Variations[edit]

All xorshift generators fail some tests out of TestU01's BigCrush test suite. This is true for 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.

xorwow[edit]

Marsaglia suggested scrambling the output by combining it with a simple additive counter modulo 232 (which he calls a "Weyl sequence" after Weyl's equidistribution theorem). This also increases the period by a factor of 232, to 2160−232:

/* The state array must be initialized to not be all zero in the first four words */
uint32_t xorwow(uint32_t state[static 5])
{
	/* Algorithm "xorwow" from p. 5 of Marsaglia, "Xorshift RNGs" */
	uint32_t s, t = state[3];
	state[3] = state[2];
	state[2] = state[1];
	state[1] = s = state[0];
	t ^= t >> 2;
	t ^= t << 1;
	state[0] = t ^= s ^ (s << 4);
	return t + (state[4] += 362437);
}

This performs well, but fails a few tests in BigCrush.[5] This generator is the default in Nvidia's CUDA toolkit.[6]

xorshift*[edit]

A xorshift* generator takes a xorshift generator and applies 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 264−1[7] and fails only the MatrixRank test of BigCrush:

#include <stdint.h>

uint64_t xorshift64star(uint64_t state[static 1]) {
	uint64_t x = state[0];	/* The state must be seeded with a nonzero value. */
	x ^= x >> 12; // a
	x ^= x << 25; // b
	x ^= x >> 27; // c
	state[0] = x;
	return x * 0x2545F4914F6CDD1D;
}

A similar generator is suggested in Numerical Recipes[8] as RanQ1, but it also fails the BirthdaySpacings test.

If the generator is modified to only return the high 32 bits, then it passes BigCrush with zero failures.[9] In fact, a reduced version with only 40 bits of internal state passes the suite, suggesting a large safety margin.[10]

Vigna[7] suggests the following xorshift1024* generator with 1024 bits of state and a maximal period of 21024−1; it however does not always pass BigCrush:

#include <stdint.h>

/* The state must be seeded so that array[] is not everywhere zero. */
struct prng_state {
	uint64_t array[16];
	int index;
}

uint64_t xorshift1024star(struct prng_state *state)
{
	int index = state->index;
	uint64_t const s = state->array[index++];
	uint64_t t = state->array[index &= 15];
	t ^= t << 31;		// a
	t ^= t >> 11;		// b
	t ^= s ^ (s >> 30);	// c
	state->array[index] = t;
	state->index = index;
	return t * (uint64_t)1181783497276652981;
}

Both generators, as it happens with all xorshift* generators, emit a sequence of 64-bit values that is equidistributed in the maximum possible dimension (except that they will never output zero for 16 calls, i.e. 128 bytes, in a row).[7]

xorshift+[edit]

Rather than using multiplication, it is possible to use addition as a faster non-linear transformation. The idea was first proposed by Saito and Matsumoto (also responsible for the Mersenne Twister) in the XSadd generator, which adds two consecutive outputs of an underlying xorshift generator based on 32-bit shifts.[11]

XSadd, however, has some weakness in the low-order bits of its output; it fails several BigCrush tests when the output words are bit-reversed. To correct this problem, Vigna[12] introduced the xorshift+ family, based on 64-bit shifts: the following xorshift128+ generator uses 128 bits of state and has a maximal period of 2128−1. It passes BigCrush, even when reversed.

#include <stdint.h>

/* The state must be seeded so that it is not all zero */
uint64_t xorshift128plus(uint64_t state[static 2]) {
	uint64_t t = state[0];
	uint64_t const s = state[1];
	state[0] = s;
	t ^= t << 23;		// a
	t ^= t >> 17;		// b
	t ^= s ^ (s >> 26);	// c
	state[1] = t;
	return t + s;
}

This generator is one of the fastest generators passing BigCrush.[4] One disadvantage of adding consecutive outputs is while the underlying xorshift128 generator is 2-dimensionally equidistributed, the associated xorshift128+ generator is only 1-dimensionally equidistributed.[12]

See also[edit]

Notes[edit]

  1. ^ In C/C++, the caret (^) represents the bitwise XOR, and the " << " and " >> " operators represent left and right bitwise shifts, respectively.

References[edit]

  1. ^ a b c Marsaglia, George (July 2003). "Xorshift RNGs". Journal of Statistical Software. 8 (14). doi:10.18637/jss.v008.i14.
  2. ^ Brent, Richard P. (August 2004). "Note on Marsaglia's Xorshift Random Number Generators". Journal of Statistical Software. 11 (5). doi:10.18637/jss.v011.i05.
  3. ^ a b Panneton, François; L'Ecuyer, Pierre (October 2005). "On the xorshift random number generators" (PDF). ACM Transactions on Modeling and Computer Simulation. 15 (4): 346–361. doi:10.1145/1113316.1113319.
  4. ^ a b Vigna, Sebastiano. "xorshift*/xorshift+ generators and the PRNG shootout". Retrieved 2014-10-25.
  5. ^ Le Floc'h, Fabien (12 January 2011). "XORWOW L'ecuyer TestU01 Results". Chase The Devil (blog). Retrieved 2017-11-02.
  6. ^ "cuRAND Testing". Nvidia. Retrieved 2017-11-02.
  7. ^ a b c Vigna, Sebastiano (July 2016). "An experimental exploration of Marsaglia's xorshift generators, scrambled" (PDF). ACM Transactions on Mathematical Software. 42 (4): 30. arXiv:1402.6246. doi:10.1145/2845077. Proposes xorshift* generators, adding a final multiplication by a constant.
  8. ^ Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 7.1.2.A. 64-bit Xorshift Method". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
  9. ^ O'Neill, Melissa E. (5 September 2014). PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation (PDF) (Technical report). Harvey Mudd College. pp. 6–8. HMC-CS-2014-0905.
  10. ^ O'Neill, Melissa E. (5 September 2014). PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation (PDF) (Technical report). Harvey Mudd College. p. 19. HMC-CS-2014-0905.
  11. ^ Saito, Mutsuo; Matsumoto, Makoto (2014). "XORSHIFT-ADD (XSadd): A variant of XORSHIFT". Retrieved 2014-10-25.
  12. ^ a b Vigna, Sebastiano (May 2017). "Further scramblings of Marsaglia's xorshift generators" (PDF). Journal of Computational and Applied Mathematics. 315 (C): 175–181. arXiv:1404.0390. doi:10.1016/j.cam.2016.11.006. Describes xorshift+ generators, a generalization of XSadd.

Further reading[edit]