Using Faster Psudo-Random Generator: XorShift

Computers cannot generate (or very difficult) true random numbers. In practise, psudo-random generators are used. To avoid ‘patterns’ for generated ‘random’ numbers, a seed is often used to re-arrange the sequence. For example,

1
2
3
4
5
6
7
8

#include <stdlib.h>
#include <time.h>
 
int main() {
  srand (time(NULL)); // seed
  cout << rand() << endl; // print a random number between 0 and RAND_MAX
  return 0;
}

#include <stdlib.h>
#include <time.h>

int main() {
  srand (time(NULL)); // seed
  cout << rand() << endl; // print a random number between 0 and RAND_MAX
  return 0;
}

Modern random generators/algorithms are already good enough to ensure a high level of randomness. However, they might be slow. In case you want to generate random numbers a million times (for instance, at innermost loops), the performance of entire application depends heavily on such random generators.

XorShift should be another options that can be quite good to consider. The XorShift is developed by George Marsagli and it is a random generator that executes faster and uses less space. Its principle is based on binary XOR shift which is invertible.

The parameters have to be carefully chosen in order to achieve a longer period (sequence) of the random numbers. The following XORShift has a period of and can be suitable in most daily uses.

1
2
3
4
5
6
7
8
9
10

uint32_t xor128(void) {
  static uint32_t x = 123456789;
  static uint32_t y = 362436069;
  static uint32_t z = 521288629;
  static uint32_t w = 88675123;
  uint32_t t;
  t = x ^ (x << 11);   
  x = y; y = z; z = w;   
  return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}

uint32_t xor128(void) {
  static uint32_t x = 123456789;
  static uint32_t y = 362436069;
  static uint32_t z = 521288629;
  static uint32_t w = 88675123;
  uint32_t t;
  t = x ^ (x << 11);   
  x = y; y = z; z = w;   
  return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}

Obviously, this is extremely fast by only using integer operations (shift, or etc). But how do we know it truly generates ‘random’ numbers like the ‘rand()’ we use a lot as well?

We can generate a bmp picture and see easily if it has any pattern. If no clear pattern is observed, then it is a good-enough random generator.

For C++ to write a BMP file fast, we can use C++ BMP Library

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include "bitmap_image.hpp"
 
using namespace std;
 
uint32_t xor128(void) {
  static uint32_t x = 123456789;
  static uint32_t y = 362436069;
  static uint32_t z = 521288629;
  static uint32_t w = 88675123;
  uint32_t t;
  t = x ^ (x << 11);   
  x = y; y = z; z = w;   
  return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}
 
int main()
{
   bitmap_image image(500, 500);
   image_drawer draw(image);
 
   const unsigned int width  = image.width();
   const unsigned int height = image.height();
   for (std::size_t y = 0; y < height; ++y)
   {
      for (std::size_t x = 0; x < width; ++x)       
      {         
            color = xor128(); // random         
            image.set_pixel(x, y, color & 0xFF, (color >> 8) & 0xFF, (color >> 16) & 0xFF);
      }
   }
   image.save_image("output.bmp");
   return 0;
}

#include "bitmap_image.hpp"

using namespace std;

uint32_t xor128(void) {
  static uint32_t x = 123456789;
  static uint32_t y = 362436069;
  static uint32_t z = 521288629;
  static uint32_t w = 88675123;
  uint32_t t;
  t = x ^ (x << 11);   
  x = y; y = z; z = w;   
  return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}

int main()
{
   bitmap_image image(500, 500);
   image_drawer draw(image);

   const unsigned int width  = image.width();
   const unsigned int height = image.height();
   for (std::size_t y = 0; y < height; ++y)
   {
      for (std::size_t x = 0; x < width; ++x)       
      {         
            color = xor128(); // random         
            image.set_pixel(x, y, color & 0xFF, (color >> 8) & 0xFF, (color >> 16) & 0xFF);
      }
   }
   image.save_image("output.bmp");
   return 0;
}

and well, the above C++ code produces a random picture (below compressed and resized a little bit) base on such fast random generator XorShift

No clear pattern can be observed by the following BMP, thus XorShift achieves a high level of randomness and can be executed in a short amount of time on modern computing architectures.

Reference:

[1] http://en.wikipedia.org/wiki/Xorshift

–EOF (Coding For Speed) —