Does anyone know of a good random number generator in C? I know of the
random generators in Numerical Recipes. Are there other good sources?
Thank you in advance.
David
C provides the rand() function, but there are no
guarantees on its "goodness."
There are plenty of other generators that can be
implemented in C -- or in C++, or Pascal, or Ada, or
Fortran, or Lisp, or perl, or what-have-you. All of
which means that your question isn't "a C question"
and really doesn't belong here.
<off-topic>
http://random.mat.sbg.ac.at/news/
</off-topic>
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
A web search will turn up stuff like this:
http://www.math.keio.ac.jp/~matumoto/emt.html
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. FAQ: ftp://cap.connx.com/pub/Chess%20Analysis%20Project%20FAQ.htm
Hi,
Thanks for telling me so many good random number generators.
However, may I know where I can find the routines you are referring to?
For example, cong(void), MWC256(void) and CMWC4096(void). Thank you in
advance.
David
> 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);}
...snipped...
[snipped irrelevant part - please don't top-post]
> ...snipped... [relevant part - that was dumb]
George already provided the code; you snipped it in your reply.
Find his post again and read it, looking for the part where he
gives you the code. Cut and paste.
-Arthur
Sorry for my mistake. I have found the codes in George's post. Thank you.
David
> -Arthur
I like those.
Thank you.
--
pete
If you are using Linux, you can read from /dev/random or,
/dev/urandom ( They generate random numbers based on the input of
hardware devicesm, such as mouse, or keyboard.
Siddharth.
"Dann Corbit" <dco...@connx.com> wrote in message news:<b9rae...@enews3.newsguy.com>...