Need a good RNG and a LCG, both with a max period >= 31 bits

[Adem24]

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

 

[Adem24]

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.

 

[Adem24]

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.

[..]

Have you tried boobling for it?

Yes, but I need expert advice.

 

[robertwessel2]

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.

 

[Bill Cox]

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.

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.

 

[Dan]

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

 

[Dan]

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.

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.

 

[rahul]

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

/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

 

[James Kanze]

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?

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

 

[Joseph Ashwood]

/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

 

[gpderetta]

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,

 

[Lionel B]

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.jp/~m-mat/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.

 

[Ilmari Karonen]

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

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

 

[Juha Nieminen]

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

 

[Juha Nieminen]

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.

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.

 

[Phil Carmody]

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

 

[Richard Tobin]

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

 

[Phil Carmody]

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

 

[Juha Nieminen]

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.

 

[Phil Carmody]

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.

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