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 programmaticall y
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]

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

"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 programmaticall y 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 programmaticall y
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

[Eric Sosman]

Re: Need a good RNG and a LCG, both with a max period &gt;= 31 bits

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 programmaticall y
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
esosman@ieee-dot-org.invalid

[robertwessel2@yahoo.com]

Re: Need a good RNG and a LCG, both with a max period &gt;= 31 bits

On Jun 10, 2:17 pm, "Adem24" <ade...@nospamm please.org.inva lidwrote:

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.rando m-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]

Re: Need a good RNG and a LCG, both with a max period &gt;= 31 bits

On Jun 10, 5:30 pm, "robertwess...@ yahoo.com"
<robertwess...@ yahoo.comwrote:

On Jun 10, 2:17 pm, "Adem24" <ade...@nospamm please.org.inva lidwrote:
>

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.rando m-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
cryptographical ly 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.ne t. Wikipedia has a good description.

[CBFalconer]

Re: Need a good RNG and a LCG, both with a max period &gt;= 31 bits

Bill Cox wrote:

<robertwess...@ yahoo.comwrote:

>"Adem24" <ade...@nospamm please.org.inva lidwrote:
>>

.... 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
cryptographical ly 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.ne t. 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 **

[Dan]

Re: Need a good RNG and a LCG, both with a max period &gt;= 31 bits

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

Re: Need a good RNG and a LCG, both with a max period &gt;= 31 bits

correction:
- The "RAND_MAX" of these generators should be >= 31 bits and <= 64 bits.
Even better if this can be set programmaticall y 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.

[David Eather]

Re: Need a good RNG and a LCG, both with a max period &gt;= 31 bits

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 programmaticall y
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

[rahul]

Re: Need a good RNG and a LCG, both with a max period &gt;= 31 bits

On Jun 11, 12:17 am, "Adem24" <ade...@nospamm please.org.inva lid>
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 programmaticall y
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 Cryptographical ly 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]

Re: Need a good RNG and a LCG, both with a max period &gt;= 31 bits

On Jun 11, 11:08 am, rahul <rahulsin...@gm ail.comwrote:

On Jun 11, 12:17 am, "Adem24" <ade...@nospamm please.org.inva lid>
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 programmaticall y
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 Cryptographical ly 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:james.kan ze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

[Joseph Ashwood]

Re: Need a good RNG and a LCG, both with a max period &gt;= 31 bits

"rahul" <rahulsinner@gm ail.comwrote in message
news:ff4e4278-6f6a-473b-90cd-1501c124505c@i3 6g2000prf.googl egroups.com...

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

/dev/random is considered Cryptographical ly 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]

Re: Need a good RNG and a LCG, both with a max period &gt;= 31 bits

On Jun 11, 12:16 pm, "Joseph Ashwood" <ashw...@msn.co mwrote:

"rahul" <rahulsin...@gm ail.comwrote in message
>
news:ff4e4278-6f6a-473b-90cd-1501c124505c@i3 6g2000prf.googl egroups.com...
>

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

/dev/random is considered Cryptographical ly 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

[Lionel B]

Re: Need a good RNG and a LCG, both with a max period &gt;= 31 bits

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

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

[rossum]

Re: Need a good RNG and a LCG, both with a max period &gt;= 31 bits

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 programmaticall y 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 programmaticall y

> 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