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

 
 
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
 
Reply With Quote
 
 
 
 
Lionel B
Guest
Posts: n/a
 
      06-12-2008
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 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.


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

--
Lionel B
 
Reply With Quote
 
 
 
 
Ilmari Karonen
Guest
Posts: n/a
 
      06-12-2008
On 11.06.2008, David Eather <(E-Mail Removed)> wrote:
>
> 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.)

--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
 
Reply With Quote
 
Juha Nieminen
Guest
Posts: n/a
 
      06-13-2008
Dan wrote:
> I don't think you will find ANY decent generator with RAND_MAX equalling the
> period! Thats ****en 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".
 
Reply With Quote
 
Juha Nieminen
Guest
Posts: n/a
 
      06-13-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.


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.
 
Reply With Quote
 
Phil Carmody
Guest
Posts: n/a
 
      06-13-2008
Juha Nieminen <(E-Mail Removed)> writes:
> Dan wrote:
>> I don't think you will find ANY decent generator with RAND_MAX equalling the
>> period! Thats ****en 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".


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
--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration
 
Reply With Quote
 
Richard Tobin
Guest
Posts: n/a
 
      06-13-2008
In article <w0r4k.958$(E-Mail Removed)>,
Juha Nieminen <(E-Mail Removed)> wrote:

> 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
--
In the selection of the two characters immediately succeeding the numeral 9,
consideration shall be given to their replacement by the graphics 10 and 11 to
facilitate the adoption of the code in the sterling monetary area. (X3.4-1963)
 
Reply With Quote
 
Phil Carmody
Guest
Posts: n/a
 
      06-13-2008
Eric Sosman <(E-Mail Removed)> writes:
> Juha Nieminen wrote:
>> Dan wrote:
>>> I don't think you will find ANY decent generator with RAND_MAX
>>> equalling the period! Thats ****en 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".

>
> ... 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
--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration
 
Reply With Quote
 
Juha Nieminen
Guest
Posts: n/a
 
      06-14-2008
Phil Carmody wrote:
> 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.
 
Reply With Quote
 
Phil Carmody
Guest
Posts: n/a
 
      06-14-2008
Juha Nieminen <(E-Mail Removed)> writes:
> Phil Carmody wrote:
>> 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.


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.

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


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
--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration
 
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