### Q(Question):

I need a good and fast random number generator (RNG),

and a linear congruential generator (LCG),

both with a max period >= 31 bits; the bigger the better.

Additional requirements:

– Must use [unsigned] integer-values only (32 or 64 bit), no floating point.

– The RNG should have passed some statistical tests.

– The "RAND_MAX" of these generators should equal the period.

– The LCG should of course generate each number only once in a period.

– The period of the LCG should easily be changable programmatically

for at least any n of 2^n upto the max possible n.

– They must be written in C or C++.

Which RNG and LCG can you recommend which satisfy these requirements?

TIA

### A(Answer):

"Adem24" wrote:

>

I need a good and fast random number generator (RNG),

and a linear congruential generator (LCG),

both with a max period >= 31 bits; the bigger the better.Additional requirements:

– Must use [unsigned] integer-values only (32 or 64 bit), no floating point.

– The RNG should have passed some statistical tests.

– The "RAND_MAX" of these generators should equal the period.

correction:

– The "RAND_MAX" of these generators should be >= 31 bits and <= 64 bits.

Even better if this can be set programmatically to any number of bits up to the max.

– The LCG should of course generate each number only once in a period.

– The period of the LCG should easily be changable programmatically

for at least any n of 2^n upto the max possible n.

– They must be written in C or C++.Which RNG and LCG can you recommend which satisfy these requirements?

TIA

### A(Answer):

Adem24 wrote:

I need a good and fast random number generator (RNG),

and a linear congruential generator (LCG),

both with a max period >= 31 bits; the bigger the better.Additional requirements:

– Must use [unsigned] integer-values only (32 or 64 bit), no floating point.

– The RNG should have passed some statistical tests.

– The "RAND_MAX" of these generators should equal the period.

– The LCG should of course generate each number only once in a period.

– The period of the LCG should easily be changable programmatically

for at least any n of 2^n upto the max possible n.

– They must be written in C or C++.Which RNG and LCG can you recommend which satisfy these requirements?

http://random.mat.sbg.ac.at/news/

Follow-ups set to sci.crypt only. I’m not certain the

question is topical there, but seems more likely to be so

than on comp.lang.c or comp.lang.c++, at least not until

you’ve chosen an algorithm and are trying to implement it.

—

Eric Sosman

es*****@ieee-dot-org.invalid

### A(Answer):

On Jun 10, 2:17*pm, "Adem24" <ade…@nospammplease.org.invalidwrote:

I need a good and fast random number generator (RNG),

and a linear congruential generator (LCG),

both with a max period >= 31 bits; the bigger the better.Additional requirements:

– Must use [unsigned] integer-values only (32 or 64 bit), no floating point.

– The RNG should have passed some statistical tests.

– The "RAND_MAX" of these generators should equal the period.

(…)

This is off topic here – sci.crypt or sci.crypt.random-numbers are

better bets.

But I’d point out that a RAND_MAX equal to the period implies a very

significant bias in the numbers generated near the end of the period,

and is rarely the sign of a good PRNG.

### A(Answer):

On Jun 10, 5:30*pm, "robertwess…@yahoo.com"

<robertwess…@yahoo.comwrote:

On Jun 10, 2:17*pm, "Adem24" <ade…@nospammplease.org.invalidwrote:

and a linear congruential generator (LCG),

both with a max period >= 31 bits; the bigger the better.Additional requirements:

– Must use [unsigned] integer-values only (32 or 64 bit), no floating point.

– The RNG should have passed some statistical tests.

– The "RAND_MAX" of these generators should equal the period.

(…)This is off topic here – sci.crypt or sci.crypt.random-numbers are

better bets.But I’d point out that a RAND_MAX equal to the period implies a very

significant bias in the numbers generated near the end of the period,

and is rarely the sign of a good PRNG.

The ARC-4 algorithm generates random numbers which are basically

cryptographically random. It takes a gigabyte of output before

there’s enough to determine that the data is not truly random. It’s

super simple and super fast. One implementation is at

tinycrypt.sf.net. Wikipedia has a good description.

### A(Answer):

Bill Cox wrote:

<robertwess…@yahoo.comwrote:

>"Adem24" <ade…@nospammplease.org.invalidwrote:

…. snip …

>>

>>Additional requirements:

– Must use [unsigned] integer-values only (32 or 64 bit), no

floating point.

– The RNG should have passed some statistical tests.

– The "RAND_MAX" of these generators should equal the period.

…. snip …

>>

But I’d point out that a RAND_MAX equal to the period implies a

very significant bias in the numbers generated near the end of

the period, and is rarely the sign of a good PRNG.The ARC-4 algorithm generates random numbers which are basically

cryptographically random. It takes a gigabyte of output before

there’s enough to determine that the data is not truly random.

It’s super simple and super fast. One implementation is at

tinycrypt.sf.net. Wikipedia has a good description.

Try the Mersenne twister. You can find it in portable C code

within nmalloc.zip on my download section (see below) as cokusmt.c

and cokusmt.h. The twister is a well known system with excellent

performance.

The code has never been used on a system with an unsigned long of

other than 32 bits, and I have thus never bothered to check it. I

stuck in an ‘error’ alert. You may need to disable that.

—

[mail]: Chuck F (cbfalconer at maineline dot net)

[page]: <http://cbfalconer.home.att.net>

Try the download section.

** Posted from http://www.teranews.com **

### A(Answer):

– The "RAND_MAX" of these generators should equal the period.

Which RNG and LCG can you recommend which satisfy these requirements?

TIA

I don’t think you will find ANY decent generator with RAND_MAX equalling the

period! Thats fucken rediculous.

### A(Answer):

correction:

– The "RAND_MAX" of these generators should be >= 31 bits and <= 64 bits.

Even better if this can be set programmatically to any number of bits up

to the max.

>Which RNG and LCG can you recommend which satisfy these requirements?

TIA

I would recommend Merseene-Twister, Period is something like 2^33770 its

fast, has a resonably small footprint. Returns random 32bit ints that can be

joined to 64bit if you want.

### A(Answer):

Adem24 wrote:

and a linear congruential generator (LCG),

both with a max period >= 31 bits; the bigger the better.Additional requirements:

– Must use [unsigned] integer-values only (32 or 64 bit), no floating point.

– The RNG should have passed some statistical tests.

– The "RAND_MAX" of these generators should equal the period.

– The LCG should of course generate each number only once in a period.

– The period of the LCG should easily be changable programmatically

for at least any n of 2^n upto the max possible n.

– They must be written in C or C++.Which RNG and LCG can you recommend which satisfy these requirements?

TIA

For a maximal period LCG n(i) = K*n(i-1) + C you need

K-1 mod 4 = 0

and

C relatively prime to K

### A(Answer):

On Jun 11, 12:17 am, "Adem24" <ade…@nospammplease.org.invalid>

wrote:

and a linear congruential generator (LCG),

both with a max period >= 31 bits; the bigger the better.Additional requirements:

– The RNG should have passed some statistical tests.

– The "RAND_MAX" of these generators should equal the period.

– The LCG should of course generate each number only once in a period.

– The period of the LCG should easily be changable programmatically

for at least any n of 2^n upto the max possible n.

– They must be written in C or C++.Which RNG and LCG can you recommend which satisfy these requirements?

TIA

/dev/random is considered Cryptographically Secure Pseduo-Random

number generator.

But I am not aware of its period. And you don’t have the source code

for it.

Its implemented in kernel and you will have to manually browse through

the

code to get the algorithm. It uses the noise from the device drivers.

For details: man 4 random

### A(Answer):

On Jun 11, 11:08 am, rahul <rahulsin…@gmail.comwrote:

On Jun 11, 12:17 am, "Adem24" <ade…@nospammplease.org.invalid>

wrote:I need a good and fast random number generator (RNG), and a

linear congruential generator (LCG), both with a max period>= 31 bits; the bigger the better.

Additional requirements:

– The RNG should have passed some statistical tests.

– The "RAND_MAX" of these generators should equal the period.

– The LCG should of course generate each number only once in a period.

– The period of the LCG should easily be changable programmatically

for at least any n of 2^n upto the max possible n.

– They must be written in C or C++.

Which RNG and LCG can you recommend which satisfy these requirements?

/dev/random is considered Cryptographically Secure

Pseduo-Random number generator. But I am not aware of its

period. And you don’t have the source code for it. Its

implemented in kernel and you will have to manually browse

through the code to get the algorithm. It uses the noise from

the device drivers.

/dev/random is only available on some Unix systems, and it is

not (normally, at least) a pseudo-random generator, but rather

provides access to a truly random source. It can also be

painfully slow, since it must wait for sufficient entropy; it’s

very useful for getting a random number to seed an RNG, but it’s

probably too slow for any extended use.

The original posting is cross-posted to both comp.lang.c and

comp.lang.c++, so I don’t know which language the original

poster uses—if it’s C++, Boost has a large collection of

random number generators (which will be incorporated into the

next version of the standard).

—

James Kanze (GABI Software) email:ja*********@gmail.com

Conseils en informatique orientée objet/

Beratung in objektorientierter Datenverarbeitung

9 place Sémard, 78210 St.-Cyr-l’École, France, +33 (0)1 30 23 00 34

### A(Answer):

"rahul" <ra*********@gmail.comwrote in message

news:ff**********************************@i36g2000 prf.googlegroups.com…

>Which RNG and LCG can you recommend which satisfy these requirements?

/dev/random is considered Cryptographically Secure Pseduo-Random

number generator.

At least in a fully patched version, so make sure you update to correct the

flaw the Debian programmer introduced.

But I am not aware of its period.

It doesn’t have a period. This is because additional entropy (randomness) is

mixed into it. I don’t recall the mixing algorithm immediately but it is a

cryptographic hash so the period without entropy introduction will well

exceed the 2^31 stated, and is at least 2^64.

Joe

### A(Answer):

On Jun 11, 12:16*pm, "Joseph Ashwood" <ashw…@msn.comwrote:

"rahul" <rahulsin…@gmail.comwrote in message

news:ff**********************************@i36g2000 prf.googlegroups.com…

Which RNG and LCG can you recommend which satisfy these requirements?

/dev/random is considered Cryptographically Secure Pseduo-Random

number generator.At least in a fully patched version, so make sure you update to correct the

flaw the Debian programmer introduced.

Just to clarify:

the flaw in Debian was in the RNG of their patched OpenSSL. It had

nothing to do with the kernel provided random number generator, other

that the former used the latter.

HTH,

—

gpd

### A(Answer):

On Wed, 11 Jun 2008 17:31:24 +1000, Dan wrote:

>correction:

– The "RAND_MAX" of these generators should be >= 31 bits and <= 64

bits.

Even better if this can be set programmatically to any number of bits

up

to the max.>>Which RNG and LCG can you recommend which satisfy these requirements?

TIA

I would recommend Merseene-Twister, Period is something like 2^33770 its

fast, has a resonably small footprint. Returns random 32bit ints that

can be joined to 64bit if you want.

(That’s `Mersenne’). I’ll second the recommendation. There is also a

`native’ 64-bit version:

http://www.math.sci.hiroshima-u.ac.j…/MT/emt64.html

Additional requirements:

– The LCG should of course generate each number only once in a period.

Why `of course’? That would not be statistically sound for a uniform

random source. And impossible if the period is RAND_MAX.

– The period of the LCG should easily be changable programmatically

for at least any n of 2^n upto the max possible n.

Don’t quite follow you there… I suspect you might have problems finding

a PRNG with period specifiable with any degree of arbitrariness, as

period tends to be tightly bound to the specifics of the algorithm.

—

Lionel B

### A(Answer):

On Thu, 12 Jun 2008 10:35:12 +0000 (UTC), Lionel B <me@privacy.net>

wrote:

>On Wed, 11 Jun 2008 17:31:24 +1000, Dan wrote:

>>correction:

– The "RAND_MAX" of these generators should be >= 31 bits and <= 64

bits.

Even better if this can be set programmatically to any number of bits

up

to the max.>>>Which RNG and LCG can you recommend which satisfy these requirements?

TIAI would recommend Merseene-Twister, Period is something like 2^33770 its

fast, has a resonably small footprint. Returns random 32bit ints that

can be joined to 64bit if you want.(That’s `Mersenne’). I’ll second the recommendation. There is also a

`native’ 64-bit version:http://www.math.sci.hiroshima-u.ac.j…/MT/emt64.html

>Additional requirements:

– The LCG should of course generate each number only once in a period.

Why `of course’? That would not be statistically sound for a uniform

random source. And impossible if the period is RAND_MAX.– The period of the LCG should easily be changable programmatically

> for at least any n of 2^n upto the max possible n.

Don’t quite follow you there… I suspect you might have problems finding

a PRNG with period specifiable with any degree of arbitrariness, as

period tends to be tightly bound to the specifics of the algorithm.

Something along those lines can be done by having a range of

generators with different periods. By combining generators with

different periods you can construct further generators with longer

periods, equal to the LCM of the periods of the underlying generators.

See L’Ecuyer (1988).

rossum

### A(Answer):

On 11.06.2008, David Eather <ea****@tpg.com.auwrote:

>

For a maximal period LCG n(i) = K*n(i-1) + C you needK-1 mod 4 = 0

and

C relatively prime to K

ITYM C relatively prime to the modulus M; that is, for a power-of-two

modulus, C odd.

Which is easily proven: If the cycle length is maximal, the cycle must

include n(i) = 0 for some i. Henceforth, every n(j), j i, is a

multiple of C modulo M. Since the cycle repeats, this applies to

_all_ n(j). If C and M have a common divisor D 1, all n(j) will

also be multiples of D, and thus the cycle length can be at most M/D,

which leads to a contradiction.

(Also, for completeness, the full condition for K is that K = 1 modulo

p for every p that divides M, where p is either 4 or a prime.)

—

Ilmari Karonen

To reply by e-mail, please replace ".invalid" with ".net" in address.

### A(Answer):

Dan wrote:

I don’t think you will find ANY decent generator with RAND_MAX equalling the

period! Thats fucken rediculous.

Are you serious? Any basic linear congruential generator will have a

period equal to the maximum value. For example:

inline unsigned nextRandValue(unsigned currentValue)

{

return currentValue * 1812433253U + 12345U;

}

Ok, maybe it all comes down to your definition of "decent".

### A(Answer):

Adem24 wrote:

and a linear congruential generator (LCG),

both with a max period >= 31 bits; the bigger the better.

The ISAAC random number generator has an enormous period,

it’s cryptographically and statistically very strong, and

according to my experiments it’s even faster than the Mersenne

Twister (only a highly optimized verion of MT which uses SSE

compares in speed). It uses unsigned integers.

I have made a C++ version of the ISAAC RNG which is very

simple to use:

http://warp.povusers.org/IsaacRand.zip

As for a linear congruential generator, here are two which

have a period of 2^32:

inline unsigned nextRandValue(unsigned currentValue)

{

return currentValue * 1812433253U + 12345U;

// Another one:

//return currentValue * 0x8088405 + 1;

}

The quality is that of a basic LCG, so not extremely high.

### A(Answer):

Juha Nieminen <no****@thanks.invalidwrites:

Dan wrote:

>I don’t think you will find ANY decent generator with RAND_MAX equalling the

period! Thats fucken rediculous.Are you serious? Any basic linear congruential generator will have a

period equal to the maximum value. For example:inline unsigned nextRandValue(unsigned currentValue)

{

return currentValue * 1812433253U + 12345U;

}Ok, maybe it all comes down to your definition of "decent".

Not really. I don’t think anyone’s ever called a 32-bit

LCPRNG ‘decent’. Given that te period’s pathetically short,

and they can be predicted with absolute certainly after only

intercepting a small portion of their cycle, they’re not

just "not decent", they’re complete crap.

I’m also curious as to how much of Knuth you’ve read, such that

you’d come out with your absurd claim that *any* LCPRNG has

maximal period.

And remember, you’re xp-ing to sci.crypt – we set the bar

far higher, and happily look down on those in a state of

sin, as von Neumann would say.

Phil

—

Dear aunt, let’s set so double the killer delete select all.

— Microsoft voice recognition live demonstration

### A(Answer):

In article <w0***************@read4.inet.fi>,

Juha Nieminen <no****@thanks.invalidwrote:

Are you serious? Any basic linear congruential generator will have a

period equal to the maximum value.

And obviously no generator without some hidden state can have a period

longer than the maximal value.

— Richard

—

In the selection of the two characters immediately succeeding the numeral 9,

consideration shall be given to their replacement by the graphics 10 and 11 to

facilitate the adoption of the code in the sterling monetary area. (X3.4-1963)

### A(Answer):

Juha Nieminen wrote:

Dan wrote:

>I don’t think you will find ANY decent generator with RAND_MAX equalling the

period! Thats fucken rediculous.Are you serious? Any basic linear congruential generator will have a

period equal to the maximum value. For example:inline unsigned nextRandValue(unsigned currentValue)

{

return currentValue * 1812433253U + 12345U;

}Ok, maybe it all comes down to your definition of "decent".

… or of "period?" The generator you exhibit has a period

that is *un*equal to the maximum value generated.

—

Eric Sosman

es*****@ieee-dot-org.invalid

### A(Answer):

Eric Sosman <es*****@ieee-dot-org.invalidwrites:

Juha Nieminen wrote:

>Dan wrote:

>>I don’t think you will find ANY decent generator with RAND_MAX

equalling the period! Thats fucken rediculous.

period equal to the maximum value. For example:inline unsigned nextRandValue(unsigned currentValue)

{

return currentValue * 1812433253U + 12345U;

}Ok, maybe it all comes down to your definition of "decent".

… or of "period?" The generator you exhibit has a period

that is *un*equal to the maximum value generated.

I’ve not verified your claim, and have no reason to doubt it,

but just wanted to check that you weren’t playing a pedantic

game about attained maxima? A maximal period 32-bit PRNG would

have range and period 2^32, but a maximal value of only 2^32-1.

Phil

—

Dear aunt, let’s set so double the killer delete select all.

— Microsoft voice recognition live demonstration

### A(Answer):

Phil Carmody wrote:

Eric Sosman <es*****@ieee-dot-org.invalidwrites:

>Juha Nieminen wrote:

>>Dan wrote:

I don’t think you will find ANY decent generator with RAND_MAX

equalling the period! Thats fucken rediculous.

Are you serious? Any basic linear congruential generator will have a

period equal to the maximum value. For example:inline unsigned nextRandValue(unsigned currentValue)

{

return currentValue * 1812433253U + 12345U;

}Ok, maybe it all comes down to your definition of "decent".

… or of "period?" The generator you exhibit has a period

that is *un*equal to the maximum value generated.I’ve not verified your claim, and have no reason to doubt it,

but just wanted to check that you weren’t playing a pedantic

game about attained maxima? A maximal period 32-bit PRNG would

have range and period 2^32, but a maximal value of only 2^32-1.

Exactly. And if my assertion is "a pedantic game," what

label should be applied to Nieminen’s?

"All integers are odd." "No, only some of them are."

"Oh, you’re just playing a pedantic game."

More to the point (and still off-topic for at least two

of the newsgroups; follow-ups set to sci.crypt only), the

O.P.’s requirements for "a max period" and "The `RAND_MAX’

of these generators should equal the period" are necessarily

in conflict, and suggest that the O.P. needs to de-confuse

himself.

### A(Answer):

Phil Carmody wrote:

Not really. I don’t think anyone’s ever called a 32-bit

LCPRNG ‘decent’. Given that te period’s pathetically short,

and they can be predicted with absolute certainly after only

intercepting a small portion of their cycle, they’re not

just "not decent", they’re complete crap.

Cryptography and hashing are not the only usages for RNGs. Simple

linear congruential generators like the one I provided are often used

for simple RNGs used in small games, etc. In that environment a cycle of

2^32 is more than enough, and predictability is not an issue.

I’m also curious as to how much of Knuth you’ve read, such that

you’d come out with your absurd claim that *any* LCPRNG has

maximal period.

You misunderstood what I said. When I said "any basic LCG" I referred

to the ones in common use.

### A(Answer):

Juha Nieminen <no****@thanks.invalidwrites:

Phil Carmody wrote:

>Not really. I don’t think anyone’s ever called a 32-bit

LCPRNG ‘decent’. Given that te period’s pathetically short,

and they can be predicted with absolute certainly after only

intercepting a small portion of their cycle, they’re not

just "not decent", they’re complete crap.Cryptography and hashing are not the only usages for RNGs. Simple

linear congruential generators like the one I provided are often used

for simple RNGs used in small games, etc. In that environment a cycle of

2^32 is more than enough, and predictability is not an issue.

However, he did post to sci.crypt. That’s the context

within which I’m answering. If I’d have seen it on a

games programming newsgroup, I’d have had a different

answer.

>I’m also curious as to how much of Knuth you’ve read, such that

you’d come out with your absurd claim that *any* LCPRNG has

maximal period.You misunderstood what I said. When I said "any basic LCG" I referred

to the ones in common use.

However, in all 3 newsgroups pedantry is almost always useful.

Sloppy C is bad C, Sloppy C++ is bad C++, and sloppy crypto

is bad crypto. Hence Eric’s reply which way out-pedants mine,

and was still justified.

Phil

—

Dear aunt, let’s set so double the killer delete select all.

— Microsoft voice recognition live demonstration