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,
csis.hku.hk/~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
x=123456789,y=362436069,z=521288629,w=88675123,v=886756453;
/* 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;
i=(i+1)&4095;
t=a*Q[i]+c;
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