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

Discussion in 'C Programming' started by Adem24, Jun 10, 2008.

  1. Adem24

    Adem24 Guest

    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, Jun 10, 2008
    #1
    1. Advertising

  2. Adem24

    Adem24 Guest

    "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, Jun 10, 2008
    #2
    1. Advertising

  3. Adem24

    Guest

    On Jun 10, 2:17 pm, "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.
    >(...)



    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.
    , Jun 10, 2008
    #3
  4. Adem24

    Bill Cox Guest

    On Jun 10, 5:30 pm, ""
    <> wrote:
    > On Jun 10, 2:17 pm, "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.
    > >(...)

    >
    > 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.
    Bill Cox, Jun 10, 2008
    #4
  5. Adem24

    Dan Guest


    > - 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, Jun 11, 2008
    #5
  6. Adem24

    Dan Guest


    > 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.
    Dan, Jun 11, 2008
    #6
  7. Adem24

    rahul Guest

    On Jun 11, 12:17 am, "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 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
    rahul, Jun 11, 2008
    #7
  8. Adem24

    James Kanze Guest

    On Jun 11, 11:08 am, rahul <> wrote:
    > On Jun 11, 12:17 am, "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 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:
    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
    James Kanze, Jun 11, 2008
    #8
  9. "rahul" <> wrote in message
    news:...
    >> 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
    Joseph Ashwood, Jun 11, 2008
    #9
  10. Adem24

    gpderetta Guest

    On Jun 11, 12:16 pm, "Joseph Ashwood" <> wrote:
    > "rahul" <> wrote in message
    >
    > news:...
    >
    > >> 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
    gpderetta, Jun 11, 2008
    #10
  11. Adem24

    Lionel B Guest

    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.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 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
    Lionel B, Jun 12, 2008
    #11
  12. On 11.06.2008, David Eather <> 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.
    Ilmari Karonen, Jun 12, 2008
    #12
  13. Dan wrote:
    > I don't think you will find ANY decent generator with RAND_MAX equalling the
    > period! Thats fucken 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".
    Juha Nieminen, Jun 13, 2008
    #13
  14. 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.
    Juha Nieminen, Jun 13, 2008
    #14
  15. Adem24

    Phil Carmody Guest

    Juha Nieminen <> writes:
    > Dan wrote:
    >> I don't think you will find ANY decent generator with RAND_MAX equalling the
    >> period! Thats fucken 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
    Phil Carmody, Jun 13, 2008
    #15
  16. In article <w0r4k.958$>,
    Juha Nieminen <> 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)
    Richard Tobin, Jun 13, 2008
    #16
  17. Adem24

    Phil Carmody Guest

    Eric Sosman <> writes:
    > Juha Nieminen wrote:
    >> Dan wrote:
    >>> I don't think you will find ANY decent generator with RAND_MAX
    >>> equalling the period! Thats fucken 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
    Phil Carmody, Jun 13, 2008
    #17
  18. 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.
    Juha Nieminen, Jun 14, 2008
    #18
  19. Adem24

    Phil Carmody Guest

    Juha Nieminen <> 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
    Phil Carmody, Jun 14, 2008
    #19
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Summercool
    Replies:
    9
    Views:
    878
    dorayme
    Oct 23, 2007
  2. Adem24
    Replies:
    19
    Views:
    730
    Phil Carmody
    Jun 14, 2008
  3. Adem24
    Replies:
    0
    Views:
    459
    Adem24
    Jun 12, 2008
  4. Francois Grieu
    Replies:
    7
    Views:
    434
    Ben Bacarisse
    Apr 8, 2009
  5. geo
    Replies:
    5
    Views:
    353
    Tim Little
    Aug 30, 2010
Loading...

Share This Page