Problem with rand() % range+1

Discussion in 'C++' started by Rafael Cunha de Almeida, Aug 25, 2008.

  1. Hi,

    I've found several sites on google telling me that I shouldn't use

    rand() % range+1

    and I should, instead, use something like:

    lowest+int(range*rand()/(RAND_MAX + 1.0))

    They fail to make it clear why. There seems to be less randomness in the
    lower bits or something like that. I don't know what less randomness
    would mean. Would it not be normally distributed or something like that?
    Rafael Cunha de Almeida, Aug 25, 2008
    #1
    1. Advertising

  2. Rafael Cunha de Almeida

    peter koch Guest

    On 25 Aug., 22:35, Rafael Cunha de Almeida <>
    wrote:
    > Hi,
    >
    > I've found several sites on google telling me that I shouldn't use
    >
    >         rand() % range+1
    >
    > and I should, instead, use something like:
    >
    >         lowest+int(range*rand()/(RAND_MAX + 1.0))
    >
    > They fail to make it clear why. There seems to be less randomness in the
    > lower bits or something like that. I don't know what less randomness
    > would mean. Would it not be normally distributed or something like that?


    Take an example of a random generator delivering numbers in the range
    0..99. If you want numbers in the range 0..79, your solution would
    give an expectancy of numbers 0..19 twice as high as the range 20..79.
    So your method is bad if you require an even distribution (but might
    be ok if you just want somewhat random distribution as eg for a game).
    The other method is better, but not perfect.

    /Peter
    peter koch, Aug 25, 2008
    #2
    1. Advertising

  3. Rafael Cunha de Almeida

    peter koch Guest

    On 25 Aug., 23:15, Pete Becker <> wrote:
    > On 2008-08-25 17:00:48 -0400, peter koch <> said:
    >
    >
    >
    >
    >
    > > On 25 Aug., 22:35, Rafael Cunha de Almeida <>
    > > wrote:
    > >> Hi,

    >
    > >> I've found several sites on google telling me that I shouldn't use

    >
    > >>         rand() % range+1

    >
    > >> and I should, instead, use something like:

    >
    > >>         lowest+int(range*rand()/(RAND_MAX + 1.0))

    >
    > >> They fail to make it clear why. There seems to be less randomness in the
    > >> lower bits or something like that. I don't know what less randomness
    > >> would mean. Would it not be normally distributed or something like that?

    >
    > > Take an example of a random generator delivering numbers in the range
    > > 0..99. If you want numbers in the range 0..79, your solution would
    > > give an expectancy of numbers 0..19 twice as high as the range 20..79.
    > > So your method is bad if you require an even distribution (but might
    > > be ok if you just want somewhat random distribution as eg for a game).
    > > The other method is better, but not perfect.

    >
    > Well, the other method is better in that it makes the non-randomness
    > less obvious. <g> But with the same sample ranges it still produces
    > twenty values twice as often as the rest; it's just that they're not
    > the twenty lowest ones any more.
    >

    You are right - the other method also produces twenty numbers twice as
    frequent as the first one - just spread evenly. To my embarassment, I
    must admit that I did not realise this when I replied. So much for
    perfection!

    /Peter
    peter koch, Aug 25, 2008
    #3
  4. Rafael Cunha de Almeida

    Guest

    On Aug 25, 2:05 pm, Pete Becker <> wrote:

    > The number of values that you start with has to be an exact multiple of
    > the number of values that you want to get. The way to do that is to
    > throw away some values from rand(), namely, those that exceed the
    > maximum multiple of range that's less than RAND_MAX+1. Like this:
    >
    > int mult = (RAND_MAX + 1) / range;


    There is a problem if RAND_MAX equals INT_MAX. Adding one would wrap
    the value and mult would become zero. So RAND_MAX could be casted to a
    suitable type and I think 'unsigned int' works. Or an unsigned 1 would
    work:

    int mult = (RAND_MAX + 1u) / range;

    I remember reading about this algorithm and that correction to it by
    Andrew Koenig on clc++m posts.

    > int max = range * mult;
    > int temp = rand();
    > while (max < temp)
    > temp = rand();
    > return temp % range;


    Ali
    , Aug 25, 2008
    #4
  5. Rafael Cunha de Almeida

    Guest

    On Aug 25, 3:35 pm, Rafael Cunha de Almeida <>
    wrote:
    > Hi,
    >
    > I've found several sites on google telling me that I shouldn't use
    >
    > rand() % range+1
    >
    > and I should, instead, use something like:
    >
    > lowest+int(range*rand()/(RAND_MAX + 1.0))


    Or function doing roughly the equivalent using integer math, which
    might be useful if range is large (to avoid signed integer overflow).

    > They fail to make it clear why. There seems to be less randomness in the
    > lower bits or something like that. I don't know what less randomness
    > would mean. Would it not be normally distributed or something like that?


    If rand() is implemented with a linear congruential generator f(x)=ax
    +b mod m, then it is a relatively easy automated check that the lower
    bits are in general highly correlated (given the first, the second is
    somewhat predictable). Directly verifying algebraically is harder,
    but a standard homework exercise in the field. The lowest separation
    required to demonstrate correlation is usually two through six
    invocations apart.

    More sophisticated algorithms are harder to verify, but reputedly have
    similar problems unless explicitly designed otherwise. [As an extreme
    case, the Mersenne Twister has been formally verified to not to be
    correlated across 637 consecutive invocations.]

    It's moderately unusual to use a high-quality RNG to implement rand().

    The overall results would still be as approximately uniformly
    distributed as rand(), except for unavoidable discretization errors as
    mentioned in earlier replies (which wouldn't be that large for small
    moduli since RAND_MAX should be at least 32767).
    , Aug 25, 2008
    #5
  6. Rafael Cunha de Almeida

    Guest

    On Aug 25, 4:47 pm, wrote:

    > More sophisticated algorithms are harder to verify, but reputedly have
    > similar problems unless explicitly designed otherwise. [As an extreme
    > case, the Mersenne Twister has been formally verified to not to be
    > correlated across 637 consecutive invocations.]


    Wrong: 623 consecutive invocations. Please accept my apologies.
    , Aug 26, 2008
    #6
  7. Rafael Cunha de Almeida

    Jorgen Grahn Guest

    On Mon, 25 Aug 2008 14:47:03 -0700 (PDT), <> wrote:
    > On Aug 25, 3:35 pm, Rafael Cunha de Almeida <>
    > wrote:
    >> Hi,
    >>
    >> I've found several sites on google telling me that I shouldn't use
    >>
    >> rand() % range+1

    ....
    >> They fail to make it clear why. There seems to be less randomness in the
    >> lower bits or something like that. I don't know what less randomness
    >> would mean. Would it not be normally distributed or something like that?

    >
    > If rand() is implemented with a linear congruential generator f(x)=ax
    > +b mod m, then it is a relatively easy automated check that the lower
    > bits are in general highly correlated (given the first, the second is
    > somewhat predictable).

    ....
    > It's moderately unusual to use a high-quality RNG to implement rand().


    "High-quality" is a bit too vague here. Are you saying that rand() is
    still broken in the low-order bits in many libraries? (Yeah, "broken"
    is also vague, but you know what I mean.)

    The Linux rand(3) manual says this:

    The versions of rand() and srand() in the Linux C Library use
    the same random number generator as random() and srandom(), so
    the lower-order bits should be as random as the higher-order
    bits. However, on older rand() implementations, and on current
    implementations on different systems, the lower-order bits are
    much less random than the higher- order bits. Do not use this
    function in applications intended to be portable when good
    randomness is needed.

    but I have never seen anyone explicitly list over current
    implementation with this problem. I kind of assumed they were gone by
    now. Or at least, I wouldn't be surprised if they were, and what used
    to be a fact ended up as urban legent.

    See also a discussion in and around Message-ID:
    <> back in 2003.

    /Jorgen

    --
    // Jorgen Grahn <grahn@ Ph'nglui mglw'nafh Cthulhu
    \X/ snipabacken.se> R'lyeh wgah'nagl fhtagn!
    Jorgen Grahn, Sep 8, 2008
    #7
  8. Rafael Cunha de Almeida

    Jorgen Grahn Guest

    On Mon, 25 Aug 2008 14:47:03 -0700 (PDT), <> wrote:
    > On Aug 25, 3:35 pm, Rafael Cunha de Almeida <>
    > wrote:
    >> Hi,
    >>
    >> I've found several sites on google telling me that I shouldn't use
    >>
    >> rand() % range+1

    ....
    >> They fail to make it clear why. There seems to be less randomness in the
    >> lower bits or something like that. I don't know what less randomness
    >> would mean. Would it not be normally distributed or something like that?

    >
    > If rand() is implemented with a linear congruential generator f(x)=ax
    > +b mod m, then it is a relatively easy automated check that the lower
    > bits are in general highly correlated (given the first, the second is
    > somewhat predictable).

    ....
    > It's moderately unusual to use a high-quality RNG to implement rand().


    "High-quality" is a bit too vague here. Are you saying that rand() is
    still broken in the low-order bits in many libraries? (Yeah, "broken"
    is also vague, but you know what I mean.)

    The Linux rand(3) manual says this:

    The versions of rand() and srand() in the Linux C Library use
    the same random number generator as random() and srandom(), so
    the lower-order bits should be as random as the higher-order
    bits. However, on older rand() implementations, and on current
    implementations on different systems, the lower-order bits are
    much less random than the higher- order bits. Do not use this
    function in applications intended to be portable when good
    randomness is needed.

    but I have never seen anyone explicitly list over current
    implementation with this problem. I kind of assumed they were gone by
    now. Or at least, I wouldn't be surprised if they were, and what used
    to be a fact ended up as urban legent.

    See also a discussion in and around Message-ID:
    <> back in 2003.

    /Jorgen

    --
    // Jorgen Grahn <grahn@ Ph'nglui mglw'nafh Cthulhu
    \X/ snipabacken.se> R'lyeh wgah'nagl fhtagn!
    Jorgen Grahn, Sep 8, 2008
    #8
    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. Replies:
    46
    Views:
    966
    Antoon Pardon
    Jul 25, 2006
  2. Varun  Kacholia
    Replies:
    11
    Views:
    2,697
    Patricia Shanahan
    Aug 3, 2006
  3. RCR for Range.rand

    , Apr 13, 2006, in forum: Ruby
    Replies:
    0
    Views:
    147
  4. 7stud --

    rand() v. rand(0.1) ?

    7stud --, Sep 15, 2007, in forum: Ruby
    Replies:
    6
    Views:
    231
    Morton Goldberg
    Sep 16, 2007
  5. DFS
    Replies:
    133
    Views:
    1,603
    Tim Rentsch
    Jun 12, 2014
Loading...

Share This Page