good C random number generator

From: George Marsaglia (
Subject: Re: good C random number generator
Newsgroups: comp.lang.c
Date: 2003-05-13 08:55:05 PST
Organization: Florida State University
Lines: 89

Most RNGs work by keeping a certain number, say k, of the most recently generated integers, then return the next integer as a function of those k. The initial k integers, the seeds, are assumed to be randomly chosen, usually 32-bits. The period of the RNG is related to the number of choices for seeds, usually 2^(32k), so to get longer periods you need to increase k.

Probably the most common type has k=1, and needs a single seed, with each new integer a function of the previous one. An example is this congruential RNG, a form of which was the system RNG in VAXs for many years:

   static unsigned long x=123456789; /* a random initial x to be       */
                                     /* assigned by the calling program */
   unsigned long cong(void )
   { return (x=69069*x+362437);}

Simple, k=1, RNGs can perform fairly well in tests of randomness such as those in the new version of Diehard,

but experience has shown that better performances come from RNGs with k's ranging from 4 or 5 to as much as 4097.

Here is an example with k=5, period about 2^160, one of the fastest long period RNGs, returns more than 120 million random 32-bit integers/second (1.8MHz CPU), seems to pass all tests:

static unsigned long
      /* replace defaults with five random seed values in calling program */
unsigned long xorshift(void)
{unsigned long t;
 t=(x^(x>>7)); x=y; y=z; z=w; w=v;
 v=(v^(v<<6))^(t^(t<<13)); return (y+y+1)*v;}

Another example has k=257, period about 2^8222. Uses a static array Q[256] and an initial carry 'c', the Q array filled with 256 random 32-bit integers in the calling program and an initial carry c<809430660 for the multiply-with-carry operation. It is very fast and seems to pass all tests.

static unsigned long Q[256],c=362436;  /* choose random initial c<809430660 and */
                                       /* 256 random 32-bit integers for Q[]    */

unsigned long MWC256(void){
  unsigned long long t,a=809430660LL;
  static unsigned char i=255;
     t=a*Q[++i]+c; c=(t>>32);
     return(Q[i]=t);      }

The Mersenne Twister (check Google) is an excellent RNG, with k=624. But it requires an elaborate C program and is slower than many RNGs that do as well in tests, have comparable or longer periods and require only a few lines of code.

Here is a complimentary-multiply-with-carry RNG with k=4097 and a near-record period, more than 10^33000 times as long as that of the Twister. (2^131104 vs. 2^19937)

  static unsigned long Q[4096],c=362436; /* choose random initial c<809430660 and */
                                         /* 4096 random 32-bit integers for Q[]   */
  unsigned long CMWC4096(void){
  unsigned long long t, a=18782LL;
  static unsigned long i=4095;
  unsigned long x,r=0xfffffffe;
     c=(t>>32); x=t+c; if(x<c){x++;c++;}
     return(Q[i]=r-x);    }

You will find several more CMWC RNGs and comments on choice of seeds in the May 2003 Communications of the ACM.

George Marsaglia