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

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

Guest
Posts: n/a

 06-10-2008
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.

- 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

Guest
Posts: n/a

 06-10-2008
>
> 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.
>
>
> - 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

robertwessel2@yahoo.com
Guest
Posts: n/a

 06-10-2008
On Jun 10, 2:17*pm, "Adem24" <(E-Mail Removed)> 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.
>
>
> - 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
Guest
Posts: n/a

 06-10-2008
On Jun 10, 5:30*pm, "(E-Mail Removed)"
<(E-Mail Removed)> wrote:
> On Jun 10, 2:17*pm, "Adem24" <(E-Mail Removed)> 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.

>

>
> > - 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
Guest
Posts: n/a

 06-11-2008

> - 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 ****en rediculous.

Dan
Guest
Posts: n/a

 06-11-2008

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

rahul
Guest
Posts: n/a

 06-11-2008
On Jun 11, 12:17 am, "Adem24" <(E-Mail Removed)>
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.
>
>
> - 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
Guest
Posts: n/a

 06-11-2008
On Jun 11, 11:08 am, rahul <(E-Mail Removed)> wrote:
> On Jun 11, 12:17 am, "Adem24" <(E-Mail Removed)>
> 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.

> > - 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
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:(E-Mail Removed)
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

Joseph Ashwood
Guest
Posts: n/a

 06-11-2008
"rahul" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
>> 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

gpderetta
Guest
Posts: n/a

 06-11-2008
On Jun 11, 12:16*pm, "Joseph Ashwood" <(E-Mail Removed)> wrote:
> "rahul" <(E-Mail Removed)> wrote in message
>
> news:(E-Mail Removed)...
>
> >> 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