good C random number generator

4589 views
Skip to first unread message

cyberdude

unread,
May 13, 2003, 3:33:53 AM5/13/03
to
Hi everybody,

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

Frank Thomas Braun

unread,
May 13, 2003, 11:17:09 AM5/13/03
to
I don't know what a good rng is because there is no such thing. But for
simulations which fail with linear congruential generators there is a
different alternative inverse congruential generators.
see http://random.mat.sbg.ac.at/literature/#NLCG
(Peter Hellekalek).
(Every random generator has a flaw and at least one application in which
it fails!)

Eric Sosman

unread,
May 13, 2003, 11:28:16 AM5/13/03
to

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>

--
Eric....@sun.com

George Marsaglia

unread,
May 13, 2003, 11:55:05 AM5/13/03
to

"cyberdude" <quake_ea...@hotmail.com> wrote in message
news:b9q751$7jv$1...@news.ust.hk...

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


Dann Corbit

unread,
May 13, 2003, 1:36:12 PM5/13/03
to
"cyberdude" <quake_ea...@hotmail.com> wrote in message
news:b9q751$7jv$1...@news.ust.hk...


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

cyberdude

unread,
May 15, 2003, 9:44:13 PM5/15/03
to
George Marsaglia <g...@stat.fsu.edu> wrote:

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...

Arthur J. O'Dwyer

unread,
May 15, 2003, 10:30:08 PM5/15/03
to

On Fri, 16 May 2003, cyberdude wrote:
>
> 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.

[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

cyberdude

unread,
May 16, 2003, 8:56:06 AM5/16/03
to

Sorry for my mistake. I have found the codes in George's post. Thank you.

David

> -Arthur

pete

unread,
May 19, 2003, 6:25:57 PM5/19/03
to

I like those.
Thank you.

--
pete

Siddharth Kashyap

unread,
May 19, 2003, 10:22:56 PM5/19/03
to
Hi,

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>...

Reply all
Reply to author
Forward
0 new messages