4589 views

Skip to first unread message

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

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!)

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!)

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>

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

May 13, 2003, 1:36:12 PM5/13/03

to

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

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

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

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

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

to

I like those.

Thank you.

--

pete

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

Search

Clear search

Close search

Google apps

Main menu