Xorshift

The Xorshift generator is a class of modern pseudo-random number generators. It is ideally suited for use even on slow CPUs by low demands on memory and processor. The Xorshift generator in 2003, was presented by its developer George Marsaglia († 2011).

Properties

  • Simple: use only the bit shift and XOR operations;
  • Low memory requirements: just as much as for the desired period length of principle is necessary (see below);
  • Quickly with only seven bit operations, a word is generated;
  • Only suitable for small sets of random numbers: fails on some statistical tests of TestU01 Suite
  • Not cryptographically secure because the internal state is exposed.

Period length

The period length (or sequence length ) follows directly from the number of bits of the internal state to 2k -1. The presented below Xorshift -RNG has four 32 -bit words, a period length of ≈ 3.4 × 2128-1 1038 words. Such period length is sufficient for all practical requirements. By the start value the sequence can be moved cyclically.

Initialization

The internal state vector (in this case, the variables x, y, z, w ) may not be initialized with zeros only, but must contain at least one 1-bit. Otherwise, one gets a generator of length 1 with the sequence { 0}. There can never emerge a "1" only by shift and XOR operations of a series of " 0", each step leads back to the initial state (0).

Retrieved from " bad " initialization, ie, only a few 1- bits in the state vector, the Xorshift recovered relatively quickly thanks to its small state vector. The probability to come across later on such states is negligible because of the small number of these states compared to the period length.

Implementation

Uint32_t xorshift32 () {    static uint32_t x = 314 159 265;    x ^ = x << 13;    x ^ = x >> 17;    x ^ = x << 5;    return x; }   uint64_t xorshift64 () {    static uint64_t x = 88172645463325252ull;    x ^ = x << 13;    x ^ = x >> 7;    x ^ = x << 17;    return x; }   uint32_t xorshift128 () {    static uint32_t x = 123456789;    static uint32_t y = 362 436 069;    static uint32_t z = 521 288 629;    static uint32_t w = 88,675,123;      uint32_t t = x ^ (x << 11);    x = y; y = z; z = w;    w ^ = ( w >> 19) ^ t ^ ( t >> 8);      return w; } Comparison with the rand ( ) function from libc

The rand in C ( and C ) standard available () function in Linux ( glibc ), and Windows implements a linear congruential generator and provides a sequence which is not even the simplest statistical tests. Thus, it is not advisable to use.

Xorshift a RNG in the form described above is provided with only five variables, a quickly -implemented alternative, however, some statistical tests fails.

Comparison with Mersenne Twister

The Xorshift generator is the Mersenne Twister at least equal, if not superior:

  • The generated bit sequences in both cases are pseudo-randomly and uniformly distributed, but there is the Mersenne Twister almost all stochastic tests.
  • The memory requirement ( for the state vector ) is significantly lower ( here: 16 bytes instead of 2496 bytes).
  • Also the Xorshift generator is almost 60 % faster.
  • In poor initialization ( that is, only a set bit in the state vector) requires the Xorshift less than 10 steps, until he delivers a uniformly distributed bit sequence. The Mersenne Twister this requires almost 800,000 steps, which is also due to the larger state vector.
  • The Xorshift -RNG has 2128-1 a shorter period length than the Mersenne Twister with 219937-1. However, again significantly larger period length of the Mersenne Twister provides not really a statement about the quality of a random number generator: A longer period means not simultaneously a higher quality or result in better statistics. Furthermore, there are other modern generators with even longer periods ( up to ≈ 2,131,086 1,039,461 ) and partly superior properties (see CMWC and WELL ).
GNU C Library Mersenne-Twister Well Equidistributed Long-period Linear List of random number generators
831410
de