Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

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

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

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

 
Reply With Quote
 
 
 
 
Adem24
Guest
Posts: n/a
 
      06-10-2008
"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


 
Reply With Quote
 
 
 
 
Adem24
Guest
Posts: n/a
 
      06-10-2008
"Victor Bazarov" <(E-Mail Removed)> 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.

 
Reply With Quote
 
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.
>
> 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.
 
Reply With Quote
 
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.

>
> > 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.
 
Reply With Quote
 
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.


 
Reply With Quote
 
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.



 
Reply With Quote
 
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.
>
> 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
 
Reply With Quote
 
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.


> > 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:(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
 
Reply With Quote
 
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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Ensuring the long period of the KISS4691 RNG. geo C Programming 5 08-30-2010 05:50 AM
construction of a uniform double RNG from a random bits RNG Francois Grieu C Programming 7 04-07-2009 11:19 PM
Need a good RNG and a LCG, both with a max period >= 31 bits Adem24 C Programming 18 06-14-2008 08:57 PM
VoIPCheap/Stunt/SIPDiscount/Et.al - Mobile - Top-up Expiry Period -- Campaign for Correct Expiry Period on Finarea VOIP Service Mobile Top-Ups News Reader UK VOIP 16 06-26-2006 05:03 PM
8-Bits vs 12 or 16 bits/pixel; When does more than 8 bits count ? Al Dykes Digital Photography 3 12-29-2003 07:08 PM



Advertisments