xorshift Pseudo Random Number Generators

mgcadmin 06-10-2021

 

Defining Randomness

When most people say a "Random number" what they really mean is "ANY number". Randomness has precise mathematical definition, and without getting too deeply into it, it means a number that does not derive from a repeating sequence which can be derived mathematically. The topic only gets deeper from there, branching into statistical distributions, etc. For most people, thats intricate of details aren't that important. And if your a theoretical mathematician, chances are you're not turning to me as a definitive resource.

In this article i am going to cover a group of algorithms for that are collectively a group of Pseudo Random Number Generators. That is: they generate numbers that have a suitable period of repetition that for all intents and purposes, the sequence they generate APPEARS random. Specifically, i will be covering the xorshift family of algorithms, as they have several desirable characteristics: they're incredibly fast, they're straight forward, and they are simple to implement.

The Linear Congruential Method

Like practically every other PNRG algorithm developed since the early 1950s, xorshift belongs to a larger family of algorithms called Linear Congruential algorithms, the most basic of which, developed by Lehmer in 1951, works like this:

class Random {
   public:
   int *a;
   int const b = 314159; //pi;
   int m;
   Random(int seed, int max, int N)  {
     a = new int[N];
     a[0] = seed;
     for (int i = 1; i < N; i++)
        a[i] = (a[i-1]*b+1) % m;
   }
};

int main() {
  Random rng(time(0), 100, 10);
  for (int i = 1; i < 10; i++)
    cout<<rng.a[i]<<" ";
  cout<<endl;
  return 0;
}

Output:

85 16 45 56 5 96 65 36 25 

 

The above algorithm will generate pseudo random numbers between 0 and m-1. The Lehmer RNG algorithm is the method that C's rand() uses, std::random_generator in C++ is based on, and various implementations can be found in almost every modern programming language major and minor. Many other common algorithms, such as the Mersenne twister, std::mt19937, are based on the Lehmer RNG. Linear Congruential algorithms are so named because they are based on algebraic linear equations. The outcome is dictated by the seed, the constant (b), and the m value. 

It is from this heritage that the xorshift family descends from.

The xorshift Family

The xorshift family of algorithms name derives from the bitwise operations it uses to produce its sequence: the exclusive or (xor) operation, and bit shifting. A variant, xoroshiro, is named for xor, shift, rotate. and produces a longer sequence period. When it comes to PRNG the longer the period the more random the sequence appears.

George Masagalia discovered the sequence and published the algorithm for it in the Journal of Statistical Software in a 2003 article titled "Xorshift RNGs". Significant research was also carried about Sebastian Vigna, especially into the xorshiro family of algorithms.

I'm going to cover three of the algorithms in the xorshift family:

1. xorshift32
2. xorshift128
3. xorshiro256**

I chose these three algorithms because they show you a clear evolutionary path between the foundational concept of the xorshift family (xorshift32) and what has been described as the "the family's general purpose PRNG": xorshiro256**. The code examples here have been adapted from the original C examples on the wikipedia article.

xorshift32

class xorshiftPRNG {
  private:
  struct xorshift_state {
     uint64_t a32;
  };
  xorshift_state state;

  public:
  xorshiftPRNG(int seed)
  {
     state.a32 = seed;
  }


  uint32_t xorshift32(int max)
  {
     uint32_t x = state.a32;
     x ^= x <<17;
     x ^= x >>7;
     x ^= x <<5;
     state.a32 = x;
     return (x % max);
  }


};

As you can see it works via a very simple series of xor and shift's, which is why it is such a fast algorithm: its not mathematically intensive. The modulo operator, which is used soley to confine the output to a given range. Yet still, it generates very reasonably random PRN's:

int main()
{
   xorshiftPRNG xorrand(time(0));d
   for (i = 0; i < 10; i++)
   {
     cout<<xorrand.xorshift32(100)<<" ";
   }
   cout<<endl;
   return 0;
}

Output:

98 56 32 77 7 23 15 36 88 44 

 

xorshift128

class xorshiftPRNG {
   private:
   struct xorshift_state {
     uint32_t a128[4];
   };
   xorshift_state state;
   public:
   xorshiftPRNG(int seed)
   {
     state.a128[0] = seed;
     state.a128[1] = seed*2;
     state.a128[2] = seed/3;
     state.a128[3] = seed+31;
   }

   uint32_t xorshift128(int max)
   {
     uint32_t t = state.a128[1];
     t ^= t << 11U;
     t ^= t >> 8U;
     state.a128[1] = state.a128[2];
     state.a128[2] = state.a128[3];
     state.a128[3] = state.a128[0];
     state.a128[0] ^= state.a128[0] >> 19U;
     state.a128[0] ^= t;
     return (state.a128[0] % max);
    } 
};

The main difference between xorshift32 and xorshift128, obviously is the number of bits being tossed around, we do sort of a round robin 32bit shift by swapping array values, before continuing the xoring. Of course, the more bits being shuffled, the longer the period: xorshift128 achieves a period of 2^61-1 . Thats a BIG number.

xorshiro256**

This is the algorithm that Marsagalia recommends for general purpose prng. xorshiro256 introduced a rotation 64 bit rotation to the algorithm that the other xorshift algorithms demonstrated do not utilize which is why this algorithm is called xorshiro and not xorshift.

class xorshiroPNRG {
private:
struct xorshiro_state {
uint64_t a[4];
};
xorshiro_state state;
public:
  int index;
  xorshiroPNRG(int seed)
  {
    state.a[0] = seed;
    state.a[1] = seed*3;
    state.a[2] = seed/5;
    state.a[3] = seed+(seed/2);
  }
  uint64_t rotate(uint64_t x, int k)
  {
    return (x <<k) | (x >> (64 - k));
  }

  uint64_t xorshiro256(int max)
  {
    uint64_t const t = state.a[1] << 17;
    uint64_t *a = state.a;
    a[2] ^= a[0];
    a[3] ^= a[1];
    a[1] ^= a[2];
    a[0] ^= a[3];
    a[2] ^= t;
    a[3] = rotate(a[3], 45);
    return (a[0]%max);
  }
};

Keep in mind that the entire family of algorithms are highly "tuneable", the shift values, the seed values can all be adjusted, so i encourage you to play around and see what you come with. It's fun to see what changes result in recognizable patterns, and what changes appear to make a more uniform randomness, theres alot of wiggle room!

The Take Away

There are loads and loads of PRNG algorithms, some easier than others, some faster than others, but one thing is absolutely certain: the results are all based on highly complex math. The best bet if you just need a plug and play solution is to use your languages built in algorithms: std::mt19337 in C++, C's rand(), Java's Math.random(), etc, etc. I dont mean to discourage you, by all means go out and implement and study, i do all the time. But ALOT of careful thought and testing has gone in to programming languages standard library prng.

 

 

---