G
geo
I have been asked to recommend an RNG
(Random Number Generator) that ranks
at or near the top in all of the categories:
performance on tests of randomness,
length of period, simplicity and speed.
The most important measure, of course, is
performance on extensive tests of randomness, and for
those that perform well, selection may well depend
on those other measures.
The following KISS version, perhaps call it KISS4691,
seems to rank at the top in all of those categories.
It is my latest, and perhaps my last, as, at age 86,
I am slowing down.
Compiling and running the following commented
C listing should produce, within about four seconds,
10^9 calls to the principal component MWC(), then
10^9 calls to the KISS combination in another ~7 seconds.
Try it; you may like it.
George Marsaglia
/*
The KISS4691 RNG, a Keep-It-Simple-Stupid combination of
MWC (Multiply-With-Carry), Congruential and Xorshift sequences.
Expressed as a simple MWC() function and C macros
#define CNG ( xcng=69069*xcng+123 )
#define XS ( xs^=(xs<<13), xs^=(xs>>17), xs^=(xs<<5) )
#define KISS ( MWC()+CNG+XS )
but easily expressed in other languages, with a slight
complication for signed integers.
With its immense period, >10^45000, and speed: MWC()s at
around 238 million/sec or full KISSes at around 138 million,
there are few RNGs that do as well as this one
on tests of randomness and are comparable in even one
of the categories: period, speed, simplicity---not to
mention comparable in all of them.
The MWC4691 sequence x[n]=8193*x[n-4691]+carry mod b=2^32
is based on p=8193*b^4691-1, period ~ 2^150124 or 10^45192
For the MWC (Multiply-With-Carry) process, given a current
x and c, the new x is (8193*x+c) mod b,
the new c is the integer part of (8193*x+c)/b.
The routine MWC() produces, in reverse order, the base-b=2^32
expansion of some j/p with 0<j<p=8193*2^150112-1 with j
determined by the 64 bits of seeds xcng and xs, or more
generally, by 150112 random bits in the Q[] array.
*/
static unsigned long xs=521288629,xcng=362436069,Q[4691];
unsigned long MWC(void) /*takes about 4.2 nanosecs or 238 million/
second*/
{unsigned long t,x,i; static c=0,j=4691;
j=(j<4690)? j+1:0;
x=Q[j];
t=(x<<13)+c+x; c=(t<x)+(x>>19);
return (Q[j]=t);
}
#define CNG ( xcng=69069*xcng+123 )
#define XS ( xs^=(xs<<13), xs^=(xs>>17), xs^=(xs<<5) )
#define KISS ( MWC()+CNG+XS ) /*138 million/sec*/
#include <stdio.h>
int main()
{unsigned long i,x;
for(i=0;i<4691;i++) Q=CNG+XS;
for(i=0;i<1000000000;i++) x=MWC();
printf(" MWC result=3740121002 ?\n%22u\n",x);
for(i=0;i<1000000000;i++) x=KISS;
printf("KISS result=2224631993 ?\n%22u\n",x);
}
/*
This RNG uses two seeds to fill the Q[4691] array by
means of CNG+XS mod 2^32. Users requiring more than two
seeds will need to randomly seed Q[] in main().
By itself, the MWC() routine passes all tests in the
Diehard Battery of Tests, but it is probably a good
idea to include it in the KISS combination.
Languages requiring signed integers should use equivalents
of the same operations, except that the C statement:
c=(t<x)+(x>>19);
can be replaced by that language's version of
if sign(x<<13+c)=sign(x) then c=sign(x)+(x>>19)
else c=1-sign(t)+(x>>19)
*/
(Random Number Generator) that ranks
at or near the top in all of the categories:
performance on tests of randomness,
length of period, simplicity and speed.
The most important measure, of course, is
performance on extensive tests of randomness, and for
those that perform well, selection may well depend
on those other measures.
The following KISS version, perhaps call it KISS4691,
seems to rank at the top in all of those categories.
It is my latest, and perhaps my last, as, at age 86,
I am slowing down.
Compiling and running the following commented
C listing should produce, within about four seconds,
10^9 calls to the principal component MWC(), then
10^9 calls to the KISS combination in another ~7 seconds.
Try it; you may like it.
George Marsaglia
/*
The KISS4691 RNG, a Keep-It-Simple-Stupid combination of
MWC (Multiply-With-Carry), Congruential and Xorshift sequences.
Expressed as a simple MWC() function and C macros
#define CNG ( xcng=69069*xcng+123 )
#define XS ( xs^=(xs<<13), xs^=(xs>>17), xs^=(xs<<5) )
#define KISS ( MWC()+CNG+XS )
but easily expressed in other languages, with a slight
complication for signed integers.
With its immense period, >10^45000, and speed: MWC()s at
around 238 million/sec or full KISSes at around 138 million,
there are few RNGs that do as well as this one
on tests of randomness and are comparable in even one
of the categories: period, speed, simplicity---not to
mention comparable in all of them.
The MWC4691 sequence x[n]=8193*x[n-4691]+carry mod b=2^32
is based on p=8193*b^4691-1, period ~ 2^150124 or 10^45192
For the MWC (Multiply-With-Carry) process, given a current
x and c, the new x is (8193*x+c) mod b,
the new c is the integer part of (8193*x+c)/b.
The routine MWC() produces, in reverse order, the base-b=2^32
expansion of some j/p with 0<j<p=8193*2^150112-1 with j
determined by the 64 bits of seeds xcng and xs, or more
generally, by 150112 random bits in the Q[] array.
*/
static unsigned long xs=521288629,xcng=362436069,Q[4691];
unsigned long MWC(void) /*takes about 4.2 nanosecs or 238 million/
second*/
{unsigned long t,x,i; static c=0,j=4691;
j=(j<4690)? j+1:0;
x=Q[j];
t=(x<<13)+c+x; c=(t<x)+(x>>19);
return (Q[j]=t);
}
#define CNG ( xcng=69069*xcng+123 )
#define XS ( xs^=(xs<<13), xs^=(xs>>17), xs^=(xs<<5) )
#define KISS ( MWC()+CNG+XS ) /*138 million/sec*/
#include <stdio.h>
int main()
{unsigned long i,x;
for(i=0;i<4691;i++) Q=CNG+XS;
for(i=0;i<1000000000;i++) x=MWC();
printf(" MWC result=3740121002 ?\n%22u\n",x);
for(i=0;i<1000000000;i++) x=KISS;
printf("KISS result=2224631993 ?\n%22u\n",x);
}
/*
This RNG uses two seeds to fill the Q[4691] array by
means of CNG+XS mod 2^32. Users requiring more than two
seeds will need to randomly seed Q[] in main().
By itself, the MWC() routine passes all tests in the
Diehard Battery of Tests, but it is probably a good
idea to include it in the KISS combination.
Languages requiring signed integers should use equivalents
of the same operations, except that the C statement:
c=(t<x)+(x>>19);
can be replaced by that language's version of
if sign(x<<13+c)=sign(x) then c=sign(x)+(x>>19)
else c=1-sign(t)+(x>>19)
*/