Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C++ (http://www.velocityreviews.com/forums/f39-c.html)
-   -   Need a good RNG and a LCG, both with a max period >= 31 bits (http://www.velocityreviews.com/forums/t619544-need-a-good-rng-and-a-lcg-both-with-a-max-period-31-bits.html)

Adem24 06-10-2008 07:17 PM

Need a good RNG and a LCG, both with a max period >= 31 bits
 
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 06-10-2008 07:52 PM

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



Adem24 06-10-2008 07:55 PM

Re: Need a good RNG and a LCG, both with a max period >= 31 bits
 
"Victor Bazarov" <v.Abazarov@comAcast.net> wrote:
> 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.
> >
> > [..]

>
> Have you tried boobling for it?


Yes, but I need expert advice.


robertwessel2@yahoo.com 06-10-2008 09:30 PM

Re: Need a good RNG and a LCG, both with a max period >= 31 bits
 
On Jun 10, 2:17*pm, "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:
>
> - 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 06-10-2008 10:06 PM

Re: Need a good RNG and a LCG, both with a max period >= 31 bits
 
On Jun 10, 5:30*pm, "robertwess...@yahoo.com"
<robertwess...@yahoo.com> wrote:
> On Jun 10, 2:17*pm, "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:

>
> > - 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 06-11-2008 07:30 AM

Re: Need a good RNG and a LCG, both with a max period >= 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 ****en rediculous.



Dan 06-11-2008 07:31 AM

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

> 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 06-11-2008 09:08 AM

Re: Need a good RNG and a LCG, both with a max period >= 31 bits
 
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:
>
> - 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 06-11-2008 09:36 AM

Re: Need a good RNG and a LCG, both with a max period >= 31 bits
 
On Jun 11, 11:08 am, rahul <rahulsin...@gmail.com> wrote:
> 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:


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

--
James Kanze (GABI Software) email:james.kanze@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

Joseph Ashwood 06-11-2008 10:16 AM

Re: Need a good RNG and a LCG, both with a max period >= 31 bits
 
"rahul" <rahulsinner@gmail.com> wrote in message
news:ff4e4278-6f6a-473b-90cd-1501c124505c@i36g2000prf.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



All times are GMT. The time now is 10:07 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.