4-Word [pseudo] Random Generator

Generator uses only shifts and xor so it should be fast.

Math design by George Marsaglia, Professor Emeritus, Florida State University. See http://www.jstatsoft.org/v08/i14/xorshift.pdf. From Journal of Statistical Software http://www.jstatsoft.org/.

Thanks to David Sexton for posting a link in news:sci.crypt.random-numbers Message ID: 1ac1d2b9.0310251435.43d3ca44@posting.google.com

This specific generator has a period of (2^128)-1. All items are unsigned 32-bit words.

unsigned int rand32(void)
{
  temp = x ^ (x << 15);
  x = y;
  y = z;
  z = w;
  w = w ^ (w >> 21) ^ temp ^ (temp >> 4);
  return w;
}

In his paper. Dr. Marsaglia mentions 4 triples that work.  The presenter of these pages can only quote values given in the paper:

[23, 24, 3]
[ 5, 14, 1]
[ 5, 12, 29]<-- this triple is used in randomFill
[15, 4, 21] <-- this example is used in his text and rand32()

An efficient random fill follows.  Note that it calls rand32 [up to 4 times] then uses a different set of values to propagate the first 4 words.  See code for details.  And just in case it's not 100% clear if you use the following code (or, for that matter any code off a web page) that proper functionality is 100% in your hands.  I disclaim any responsibility for any faults.  Note that the 4 seed words should be ordered w, z, y, x for memcpy to work properly at the top of this function.

// Thanks to SM Ryan who provided the LV macro in news:comp.lang.c
// As given, the macro name was lvaluecast
// Message-ID: <10imenhfni9tb62@corp.supernews.com>
#define LV(type,lvalue) (*((type*)((void*)(&(lvalue)))))

void randomFill(void* dest, int len)
{
  UINT32 temp;
  if (len <= 0) return; // ie if (stupid arg) return;
  int firstLen = len;
  if (len > 16) firstLen = 16;

///////////////////////////////////////////////
// fill the first 16 bytes...
///////////////////////////////////////////////

  for(temp=(firstLen+3)>>2; temp; temp--)
  {
    rand32();
  }
  memcpy(dest, &w, firstLen);
  LV(int, dest) += firstLen;
  len -= firstLen;

///////////////////////////////////////////////
// fill whole words after the first 16 bytes
///////////////////////////////////////////////

  while (len > 3)
  {
// Notice how LV(int*,dest)[-4] is used where x is used in random()
// and pDest[-1] is used in place of w
//
// Then notice that LV(int*,dest)++ takes the place of x=y etc
//
// NB: uning [5, 12, 29] here is important because we don't want
// to fill with values that follow the future returns from rand32()
//
  temp = LV(int*,dest)[-4] ^ (LV(int*,dest)[-4] << 5);
  *LV(int*,dest)++ =
  LV(int*,dest)[-1] ^ (LV(int*,dest)[-1] >> 29) ^ temp ^ (temp >> 12);
  len -= 4;
  }
  if (len <= 0) return;

/////////////////////////////////////////////
// fill any tail
/////////////////////////////////////////////
  rand32();
  memcpy(dest, &w, len);
}

Next Topic (Lagged Fibonacci Generator)
Previous Topic
Return to Index