Xorshift


Xorshift random number generators, also called shift-register generators, are a class of pseudorandom number generators that were invented by George Marsaglia. They are a subset of linear-feedback shift registers which allow a particularly efficient implementation in software without the excessive use of sparse polynomials. 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 execution extremely efficient on modern computer architectures, but it does not benefit efficiency in a hardware implementation. Like all LFSRs, the parameters have to be chosen very carefully in order to achieve a long period.
For execution in software, xorshift generators are among the fastest PRNGs, requiring very small code and state. However, they do not pass every statistical test without further refinement. This weakness is amended by combining them with a non-linear function, as described in the original paper. Because plain xorshift generators fail some statistical tests, they have been accused of being unreliable.

Example implementation

A C version of three xorshift algorithms is 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 one has four 32-bit words of state, and period 2128−1. 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.
All use three shifts and three or four exclusive-or operations:

  1. include
struct xorshift32_state ;
/* The state must be initialized to non-zero */
uint32_t xorshift32
struct xorshift64_state ;
/* The state must be initialized to non-zero */
uint64_t xorshift64
/* struct xorshift128_state can alternatively be defined as a pair
of uint64_t or a uint128_t where supported */
struct xorshift128_state ;
/* The state must be initialized to non-zero */
uint32_t xorshift128

In case of one 64-bit word of state, there exist parameters which hold period 264−1 with two pair of exclusive-or and shift.

  1. include
struct xorshift64_state ;
uint64_t xorshift64

Non-linear variations

All xorshift generators fail some tests in the 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.
The scramblers known as and still leave weakness in the low bits, so they are intended for floating point use, where the lowest bits of floating-point numbers have a smaller impact on the interpreted value. For general purpose, the scrambler makes the LFSR generators pass in all bits.

xorwow

Marsaglia suggested scrambling the output by combining it with a simple additive counter modulo 232. This also increases the period by a factor of 232, to 2192−232:

  1. include
struct xorwow_state ;
/* The state array must be initialized to not be all zero in the first four words */
uint32_t xorwow

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

xorshift*

A generator applies an invertible multiplication as a non-linear transformation to the output of a generator, as suggested by Marsaglia. All generators emit a sequence of values that is equidistributed in the maximum possible dimension.
The following 64-bit generator has a maximal period of 264−1.

  1. include
/* xorshift64s, variant A_1 with multiplier M_32 from line 3 of table 5 */
uint64_t xorshift64star

The generator fails only the MatrixRank test of BigCrush, however if the generator is modified to return only the high 32 bits, then it passes BigCrush with zero failures. In fact, a reduced version with only 40 bits of internal state passes the suite, suggesting a large safety margin. A similar generator suggested in Numerical Recipes as RanQ1 also fails the BirthdaySpacings test.
Vigna suggests the following generator with 1024 bits of state and a maximal period of 21024−1; however, it does not always pass BigCrush. xoshiro256** is therefore a much better option.

  1. include
/* The state must be seeded so that there is at least one non-zero element in array */
struct xorshift1024s_state ;
uint64_t xorshift1024s

xorshift+

A generator can achieve an order of magnitude fewer failures than Mersenne Twister or WELL. A native C implementation of a xorshift+ generator that passes all tests from the BigCrush suite can typically generate a random number in fewer than 10 clock cycles on x86, thanks to instruction pipelining.
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 in the generator, which adds two consecutive outputs of an underlying generator based on 32-bit shifts. However, one disadvantage of adding consecutive outputs is that, while the underlying generator is 2-dimensionally equidistributed, the generator is only 1-dimensionally equidistributed.
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 introduced the family, based on 64-bit shifts. generators, even as large as, exhibit some detectable linearity in the low-order bits of their output; it passes BigCrush, but doesn't when the 32 lowest-order bits are used in reverse order from each 64-bit word. This generator is one of the fastest generators passing BigCrush.
The following generator uses 128 bits of state and has a maximal period of 2128−1.

  1. include
struct xorshift128p_state ;
/* The state must be seeded so that it is not all zero */
uint64_t xorshift128p

xorshiftr+

generator was mainly based on xorshift+ yet incorporates modifications making it significantly faster and more successful in randomness tests compared to its predecessors. It is one of the fastest generators passing all tests in TestU01's BigCrush suite. Like xorshift+, a native C implementation of a xorshiftr+ generator that passes all tests from the BigCrush suite can typically generate a random number in fewer than 10 clock cycles on x86, thanks to instruction pipelining.
Unlike, does not return the sum of two variables derived from the state using xorshift-style steps, rather it returns a single variable with the very last operation in its cycle; however, it features an addition just before returning a value, namely in the phase of adjusting the seed for the next cycle; hence the "+" in the name of the algorithm. The variable sizes, including the state, can be increased with no compromise to the randomness scores, but performance drops may be observed on lightweight devices.
The following generator uses 128 bits of state and has a maximal period of 2128−1.

  1. include
struct xorshiftr128plus_state ;
/* The state must be seeded so that it is not all zero */
uint64_t xorshiftr128plus

xoshiro

xoshiro and xoroshiro use rotations in addition to shifts. According to Vigna, they are faster and produce better quality output than xorshift.
This class of generator has variants for 32-bit and 64-bit integer and floating point output; for floating point, one takes the upper 53 bits or the upper 23 bits, since the upper bits are of better quality than the lower bits in the floating point generators. The algorithms also include a jump function, which sets the state forward by some number of steps – usually a power of two that allows many threads of execution to start at distinct initial states.
For 32-bit output, xoshiro128** and xoshiro128+ are exactly equivalent to xoshiro256** and xoshiro256+, with in place of, and with different shift/rotate constants.
More recently, the generators have been made as an alternative to the generators. They are used in some implementations of Fortran compilers such as GNU Fortran, and in Java, and Julia.

xoshiro256++

xoshiro256++ is the family's general-purpose random 64-bit number generator.
/* Adapted from the code included on Sebastiano Vigna's website */
  1. include
uint64_t rol64
struct xoshiro256pp_state ;
uint64_t xoshiro256pp

xoshiro256**

xoshiro256** uses multiplication rather than addition in its output function. It is worth noting, however, that the output function is invertible, allowing the underlying state to be trivially uncovered. It is used in GNU Fortran compiler, Lua, and the.NET framework.
/* Adapted from the code included on Sebastiano Vigna's website */
  1. include
uint64_t rol64
struct xoshiro256ss_state ;
uint64_t xoshiro256ss

xoshiro256+

xoshiro256+ is approximately 15% faster than xoshiro256**, but the lowest three bits have low linear complexity; therefore, it should be used only for floating point results by extracting the upper 53 bits.

  1. include
uint64_t rol64
struct xoshiro256p_state ;
uint64_t xoshiro256p