Random Integers from 0 to 999

Discussion in 'C Programming' started by Michael B Allen, Mar 24, 2005.

  1. Someone once posted the following macro on clc:

    #define randint(a,b) (a)+(((b)-(a)+1)*(float)rand()/RAND_MAX)

    Unfortunately it's flawed. If rand() returns RAND_MAX the result can be
    one larger than b.

    So can someone provide a *proper* macro (or function) that returns a
    random integer between (actually in) a range of values? For example
    randint(0, 999) could return:

    0
    10
    777
    999

    Mike
     
    Michael B Allen, Mar 24, 2005
    #1
    1. Advertising

  2. Michael B Allen

    Michael Mair Guest

    Michael B Allen wrote:
    > Someone once posted the following macro on clc:
    >
    > #define randint(a,b) (a)+(((b)-(a)+1)*(float)rand()/RAND_MAX)
    >
    > Unfortunately it's flawed. If rand() returns RAND_MAX the result can be
    > one larger than b.
    >
    > So can someone provide a *proper* macro (or function) that returns a
    > random integer between (actually in) a range of values? For example
    > randint(0, 999) could return:
    >
    > 0
    > 10
    > 777
    > 999


    Where is your shot at it? Without attribution, nobody knows
    from which source this comes.

    #define RANDINT(a,b) (a)+(((b)-(a)+1)*(double)rand()/(1u+RAND_MAX))

    may serve you better; note the double which serves you well
    if RAND_MAX has more digits than float can represent.
    There are other deficiencies for this approach; why don't you
    use the suggestions of, say, Lawrence Kirby (or other regulars)
    which make all values equally probable?
    Apart from that: I would rather use a function for this purpose.
    If you need many random numbers, consider filling an array and
    retrieving from there until it is "used up", then refilling.


    Cheers
    Michael
    --
    E-Mail: Mine is an /at/ gmx /dot/ de address.
     
    Michael Mair, Mar 24, 2005
    #2
    1. Advertising

  3. Michael B Allen

    Grumble Guest

    Michael B Allen wrote:

    > Someone once posted the following macro on clc:
    >
    > #define randint(a,b) (a)+(((b)-(a)+1)*(float)rand()/RAND_MAX)
    >
    > Unfortunately it's flawed. If rand() returns RAND_MAX the result can be
    > one larger than b.
    >
    > So can someone provide a *proper* macro (or function) that returns a
    > random integer between (actually in) a range of values? For example
    > randint(0, 999) could return:
    >
    > 0
    > 10
    > 777
    > 999


    int randint(int min, int max)
    {
    assert(min <= max);
    return min + rand() % (max - min + 1);
    }

    0 <= rand() <= RAND_MAX
    0 <= rand()%(max-min+1) < max-min+1
    0 <= rand()%(max-min+1) <= max-min
    min <= min+rand()%(max-min+1) <= max
     
    Grumble, Mar 24, 2005
    #3
  4. Michael B Allen

    Mark Piffer Guest

    Michael Mair wrote:
    > Michael B Allen wrote:
    > > Someone once posted the following macro on clc:
    > >
    > > #define randint(a,b) (a)+(((b)-(a)+1)*(float)rand()/RAND_MAX)
    > >
    > > Unfortunately it's flawed. If rand() returns RAND_MAX the result

    can be
    > > one larger than b.
    > >

    >
    > Where is your shot at it? Without attribution, nobody knows
    > from which source this comes.
    >
    > #define RANDINT(a,b) (a)+(((b)-(a)+1)*(double)rand()/(1u+RAND_MAX))
    >
    > may serve you better; note the double which serves you well
    > if RAND_MAX has more digits than float can represent.
    > There are other deficiencies for this approach; why don't you
    > use the suggestions of, say, Lawrence Kirby (or other regulars)
    > which make all values equally probable?
    > Apart from that: I would rather use a function for this purpose.
    > If you need many random numbers, consider filling an array and
    > retrieving from there until it is "used up", then refilling.
    >


    Unluckily, both, your and Grumble's snippet produce UB due to integer
    overflow when RAND_MAX happens to equal INT_MAX (like on all my 16-Bit
    compilers) and the arguments are (0,RAND_MAX). It looks like

    #define RANDINT(a,b)\
    ((b)-(a)==RAND_MAX?(a)+rand():(a)+rand()%((b)-(a)+1))

    will do it, although the distribution will be abysmal. Then again, for
    embedded architectures, where neither floating point nor much RAM is an
    option, I use such generators exactly for their simplicity and not the
    randomness. Most of my test data just needs to be better than
    iterative, but not truly random. Where "real" randomness is needed I go
    and ask the big boys (the mathematicians); uniform distributions won't
    cut it most of the time anyway.

    Mark
     
    Mark Piffer, Mar 24, 2005
    #4
  5. Michael B Allen

    Michael Mair Guest

    Mark Piffer wrote:
    > Michael Mair wrote:
    >
    >>Michael B Allen wrote:
    >>
    >>>Someone once posted the following macro on clc:
    >>>
    >>>#define randint(a,b) (a)+(((b)-(a)+1)*(float)rand()/RAND_MAX)
    >>>
    >>>Unfortunately it's flawed. If rand() returns RAND_MAX the result

    >
    > can be
    >
    >>>one larger than b.
    >>>

    >>
    >>Where is your shot at it? Without attribution, nobody knows
    >>from which source this comes.
    >>
    >> #define RANDINT(a,b) (a)+(((b)-(a)+1)*(double)rand()/(1u+RAND_MAX))
    >>
    >>may serve you better; note the double which serves you well
    >>if RAND_MAX has more digits than float can represent.
    >>There are other deficiencies for this approach; why don't you
    >>use the suggestions of, say, Lawrence Kirby (or other regulars)
    >>which make all values equally probable?
    >>Apart from that: I would rather use a function for this purpose.
    >>If you need many random numbers, consider filling an array and
    >>retrieving from there until it is "used up", then refilling.

    >
    > Unluckily, both, your and Grumble's snippet produce UB due to integer
    > overflow when RAND_MAX happens to equal INT_MAX (like on all my 16-Bit
    > compilers) and the arguments are (0,RAND_MAX). It looks like
    >
    > #define RANDINT(a,b)\
    > ((b)-(a)==RAND_MAX?(a)+rand():(a)+rand()%((b)-(a)+1))
    >
    > will do it, although the distribution will be abysmal. Then again, for
    > embedded architectures, where neither floating point nor much RAM is an
    > option, I use such generators exactly for their simplicity and not the
    > randomness. Most of my test data just needs to be better than
    > iterative, but not truly random. Where "real" randomness is needed I go
    > and ask the big boys (the mathematicians); uniform distributions won't
    > cut it most of the time anyway.


    You are right, I forgot to mention this particular problem and
    did not correct it; however IIRC it is covered in the mentioned
    message by Lawrence Kirby.
    If I have too much time on my hands, I will search for it.
    I still hold that writing a function is the better way; you
    can cut off the excess random values and handle special cases in a
    transparent way.

    If we speak of overkill: The Mersenne Twister should do for
    a start :)


    Cheers
    Michael
    --
    E-Mail: Mine is an /at/ gmx /dot/ de address.
     
    Michael Mair, Mar 24, 2005
    #5
  6. On Thu, 24 Mar 2005 09:30:34 +0100, Grumble
    <> wrote:

    > Michael B Allen wrote:
    >
    >> Someone once posted the following macro on clc:
    >>
    >> #define randint(a,b) (a)+(((b)-(a)+1)*(float)rand()/RAND_MAX)
    >>
    >> Unfortunately it's flawed. If rand() returns RAND_MAX the result can be
    >> one larger than b.


    The simple solution is to use (RAND_MAX+1) as the divisor. However, it
    has the same probem as below.

    >> So can someone provide a *proper* macro (or function) that returns a
    >> random integer between (actually in) a range of values? For example
    >> randint(0, 999) could return:
    >>
    >> 0
    >> 10
    >> 777
    >> 999

    >
    > int randint(int min, int max)
    > {
    > assert(min <= max);
    > return min + rand() % (max - min + 1);
    > }


    That just uses different bits to do the same thing (except that you
    corrected the "off by one" error). However, there are a number of poor
    implementations of rand() where the bottom bits are a lot more
    predictable than the higher ones (rand() % 4 returning a continuous
    repeated sequence of 0, 1, 2, 3 in one of them!).

    > 0 <= rand() <= RAND_MAX
    > 0 <= rand()%(max-min+1) < max-min+1
    > 0 <= rand()%(max-min+1) <= max-min
    > min <= min+rand()%(max-min+1) <= max


    If the range is not a submultiple of (RAND_MAX + 1) then it does not
    give equal probabilities of all of the numbers. For instance, take a
    small RAND_MAX of 7 (0 <= rand() <= 7) and a range of [0..4]:

    rand() randint()
    0 0
    1 1
    2 2
    3 3
    4 4
    5 0
    6 1
    7 2

    results 0..2 occur twice as often as 3..4. Granted that when RAND_MAX
    is very much bigger than the range the error becomes smaller, it is
    still there (the potential error is range/(RAND_MAX+1)).

    Chris C
     
    Chris Croughton, Mar 24, 2005
    #6
  7. In article <d1ttra$l46$>,
    Grumble <> wrote:
    >
    >int randint(int min, int max)
    >{
    > assert(min <= max);
    > return min + rand() % (max - min + 1);
    >}
    >
    >0 <= rand() <= RAND_MAX
    >0 <= rand()%(max-min+1) < max-min+1
    >0 <= rand()%(max-min+1) <= max-min
    >min <= min+rand()%(max-min+1) <= max


    That's a terrible way of generating "random" numbers.

    When we ask for a "random number" in the range min..max,
    we want every number within that range to occur with equal
    probability.

    The following example shows that your method does not give a
    uniformly distributed random number.

    For the sake of illustration, let's say RAND_MAX is 7.
    Suppose you want random numbers in the set {0,1,2,3,4,5}.
    Then according to your algorithm:

    rand() randint()
    0 -> 0
    1 -> 1
    2 -> 2
    3 -> 3
    4 -> 4
    5 -> 5
    6 -> 0
    7 -> 1

    Therefore the numbers 0 and 1 are twice as likely to show up
    than other numbers.

    Here is a better way:

    int randint(int min, int max)
    {
    assert(min <= max);
    return min + (int)((max-min+1.0)*rand()/(1.0+RAND_MAX));
    }

    --
    Rouben Rostamian
     
    Rouben Rostamian, Mar 24, 2005
    #7
  8. Michael B Allen

    Grumble Guest

    Rouben Rostamian wrote:

    > Grumble wrote:
    >
    >> int randint(int min, int max)
    >> {
    >> assert(min <= max);
    >> return min + rand() % (max - min + 1);
    >> }

    >
    > That's a terrible way of generating "random" numbers.
    >
    > When we ask for a "random number" in the range min..max,
    > we want every number within that range to occur with equal
    > probability.
    >
    > The following example shows that your method does not give a
    > uniformly distributed random number.
    >
    > For the sake of illustration, let's say RAND_MAX is 7.
    > Suppose you want random numbers in the set {0,1,2,3,4,5}.
    > Then according to your algorithm:
    >
    > rand() randint()
    > 0 -> 0
    > 1 -> 1
    > 2 -> 2
    > 3 -> 3
    > 4 -> 4
    > 5 -> 5
    > 6 -> 0
    > 7 -> 1
    >
    > Therefore the numbers 0 and 1 are twice as likely to show up
    > than other numbers.
    >
    > Here is a better way:
    >
    > int randint(int min, int max)
    > {
    > assert(min <= max);
    > return min + (int)((max-min+1.0)*rand()/(1.0+RAND_MAX));
    > }


    You algorithm is as "broken" as mine because of a fundamental problem:

    If you try to place 8 balls in 6 buckets, then, no matter how you slice
    and dice it, you'll end up with more balls in some buckets. The only way
    out is to discard 2 balls.

    --
    Regards, Grumble
     
    Grumble, Mar 24, 2005
    #8
  9. Michael B Allen

    CBFalconer Guest

    Michael B Allen wrote:
    >
    > Someone once posted the following macro on clc:
    >
    > #define randint(a,b) (a)+(((b)-(a)+1)*(float)rand()/RAND_MAX)
    >
    > Unfortunately it's flawed. If rand() returns RAND_MAX the result
    > can be one larger than b.


    #define ranrange(a, b) (int)((a) + rand()/((double)RAND_MAX + 1) \
    * ((b) - (a) + 1))

    assuming 0 == rand() can occur. Many systems will never return 0,
    so:

    #define ranrange(a, b) (int)((a) + (rand() - 1)/((double)RAND_MAX)
    \
    * ((b) - (a) + 1))

    (untested)

    >
    > So can someone provide a *proper* macro (or function) that returns
    > a random integer between (actually in) a range of values?
    > For example randint(0, 999) could return:
    >
    > 0
    > 10
    > 777
    > 999


    --
    "If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers." - Keith Thompson
     
    CBFalconer, Mar 24, 2005
    #9
  10. On Thu, 24 Mar 2005 15:09:47 +0000 (UTC), Rouben Rostamian
    <> wrote:

    > In article <d1ttra$l46$>,
    > Grumble <> wrote:
    >>
    >>int randint(int min, int max)
    >>{
    >> assert(min <= max);
    >> return min + rand() % (max - min + 1);
    >>}
    >>
    >>0 <= rand() <= RAND_MAX
    >>0 <= rand()%(max-min+1) < max-min+1
    >>0 <= rand()%(max-min+1) <= max-min
    >>min <= min+rand()%(max-min+1) <= max

    >
    > That's a terrible way of generating "random" numbers.
    >
    > When we ask for a "random number" in the range min..max,
    > we want every number within that range to occur with equal
    > probability.
    >
    > The following example shows that your method does not give a
    > uniformly distributed random number.
    >
    > For the sake of illustration, let's say RAND_MAX is 7.
    > Suppose you want random numbers in the set {0,1,2,3,4,5}.
    > Then according to your algorithm:
    >
    > rand() randint()
    > 0 -> 0
    > 1 -> 1
    > 2 -> 2
    > 3 -> 3
    > 4 -> 4
    > 5 -> 5
    > 6 -> 0
    > 7 -> 1
    >
    > Therefore the numbers 0 and 1 are twice as likely to show up
    > than other numbers.
    >
    > Here is a better way:
    >
    > int randint(int min, int max)
    > {
    > assert(min <= max);
    > return min + (int)((max-min+1.0)*rand()/(1.0+RAND_MAX));
    > }


    Why is that any better? Assuming your example of RAND_MAX==7, and
    wanting numbers in the set [0,5]:

    rand() randint()
    0 -> 0*6/8 0/8 -> 0
    1 -> 1*6/8 6/8 -> 0
    2 -> 2*6/8 12/8 -> 1
    3 -> 3*6/8 18/8 -> 2
    4 -> 4*6/8 24/8 -> 3
    5 -> 5*6/8 30/8 -> 3
    6 -> 6*6/8 36/8 -> 4
    7 -> 7*6/8 42/8 -> 5

    All you've done is to change it so that 0 and 3 get the extra hits
    instead of 0 and 1. OK, it looks slightly more uniform (the mean will be
    better,2.25 instead of 2, it should be 2.5) but it's still got the same
    problem of two of the numbers occuring twice as often as the others.

    A way of getting round the problem is to use an iterative method and
    discard values out of range:

    int randint(int min, int max)
    {
    unsigned range = max - min + 1;
    int bits = 1;
    int result;
    assert(range > 0 && range <= RAND_MAX);
    while (range-1 > bits)
    bits = bits*2 + 1;
    do result = rand() & bits; while (result > range);
    return result + min;
    }

    This only works if RAND_INT is 2^n - 1, but that's the case on all
    implementations I've found. It is also susceptible to the quality of
    the lower bits of rand(), which on some implementations are not very
    random...

    Chris C
     
    Chris Croughton, Mar 24, 2005
    #10
  11. Michael B Allen

    CBFalconer Guest

    Grumble wrote:
    > Rouben Rostamian wrote:
    >> Grumble wrote:
    >>
    >>> int randint(int min, int max)
    >>> {
    >>> assert(min <= max);
    >>> return min + rand() % (max - min + 1);
    >>> }

    >>

    .... snip ...
    >>
    >> For the sake of illustration, let's say RAND_MAX is 7.
    >> Suppose you want random numbers in the set {0,1,2,3,4,5}.
    >> Then according to your algorithm:
    >>
    >> rand() randint()
    >> 0 -> 0
    >> 1 -> 1
    >> 2 -> 2
    >> 3 -> 3
    >> 4 -> 4
    >> 5 -> 5
    >> 6 -> 0
    >> 7 -> 1
    >>
    >> Therefore the numbers 0 and 1 are twice as likely to show up
    >> than other numbers.
    >>
    >> Here is a better way:
    >>
    >> int randint(int min, int max)
    >> {
    >> assert(min <= max);
    >> return min + (int)((max-min+1.0)*rand()/(1.0+RAND_MAX));
    >> }

    >
    > You algorithm is as "broken" as mine because of a fundamental
    > problem:
    >
    > If you try to place 8 balls in 6 buckets, then, no matter how you
    > slice and dice it, you'll end up with more balls in some buckets.
    > The only way out is to discard 2 balls.


    Since RAND_MAX is normally much larger than (max - min) that effect
    is minimal. However, you can allow for it by:

    unsigned int ranrange(unsigned int min, unsigned int max)
    {
    unsigned int t, d, n;

    if (min > max) { /* No assert, just an interval */
    t = min; min = max; max = t;
    }
    t = max - min + 1;
    d = RAND_MAX / t;
    d *= t;
    do { /* discard the few biasing values */
    n = rand(); /* assuming rand() unbiased */
    } while (n > d);
    return min + (int)((double)t * n/(1.0 + d));
    } /* untested */

    It probably requires tweaking for the minimum return from rand,
    which may well be either 1 or 0.

    --
    "If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers." - Keith Thompson
     
    CBFalconer, Mar 24, 2005
    #11
  12. Rouben Rostamian wrote:
    > ...
    > Then according to your algorithm:
    >
    > rand() randint()
    > 0 -> 0
    > 1 -> 1
    > 2 -> 2
    > 3 -> 3
    > 4 -> 4
    > 5 -> 5
    > 6 -> 0
    > 7 -> 1
    >
    > Therefore the numbers 0 and 1 are twice as likely to show up
    > than other numbers.
    >
    > Here is a better way:
    >
    > int randint(int min, int max)
    > {
    > assert(min <= max);
    > return min + (int)((max-min+1.0)*rand()/(1.0+RAND_MAX));
    > }
    > ...


    There's absolutely no way to implement the required functionality by a
    stateless function that simply maps 'int' to 'int'. Regardless of how
    you do it, some numbers will appear with higher probability than other
    numbers. The version you provided is as "terrible" as the previous one
    for the very same reason - for the same ranges of input and output
    values some numbers will be "twice as likely to show up than other
    numbers" (you should've tested it before posting here).

    When [0, RAND_MAX] range is significantly wider than the requiested
    [min, max] range, this is not really a problem. In other cases, only a
    stateful mapping function will help.

    --
    Best regards,
    Andrey Tarasevich
     
    Andrey Tarasevich, Mar 24, 2005
    #12
  13. Michael B Allen

    Guest

    Rouben Rostamian wrote:
    > [...]
    > rand() randint()
    > 0 -> 0
    > 1 -> 1
    > 2 -> 2
    > 3 -> 3
    > 4 -> 4
    > 5 -> 5
    > 6 -> 0
    > 7 -> 1
    >
    > Therefore the numbers 0 and 1 are twice as likely to show up
    > than other numbers.
    >
    > Here is a better way:
    >
    > int randint(int min, int max) {
    > assert(min <= max);
    > return min + (int)((max-min+1.0)*rand()/(1.0+RAND_MAX));
    > }


    This solution (which, unfortunately, is endorsed by the comp.lang.c
    FAQ) is no better. As others have posted, you're up against the
    pigeon-hole principle, you can't fix it by just changing the mapping in
    some way.

    And its a real problem in practice -- RAND_MAX need not be higher than
    65535, and in most of the compilers on the most popular platform it is
    indeed exactly this. I have a more complete summary of the issue here:

    http://www.pobox.com/~qed/random.html

    ---
    Paul Hsieh
    http://www.pobox.com/~qed/
    http://bstring.sf.net/
     
    , Mar 27, 2005
    #13
  14. On 26 Mar 2005 16:50:31 -0800, wrote:

    > Rouben Rostamian wrote:

    <snip>
    > > return min + (int)((max-min+1.0)*rand()/(1.0+RAND_MAX));

    <snip>
    > This solution (which, unfortunately, is endorsed by the comp.lang.c
    > FAQ) is no better. As others have posted, you're up against the
    > pigeon-hole principle, you can't fix it by just changing the mapping in
    > some way.
    >
    > And its a real problem in practice -- RAND_MAX need not be higher than
    > 65535, and in most of the compilers on the most popular platform it is
    > indeed exactly this. I have a more complete summary of the issue here:
    >
    > http://www.pobox.com/~qed/random.html


    Need not be higher than, and often is, 32767 (= minimum INT_MAX).

    Although for a desired choice range of no more than about 30, I might
    consider the <.1% nonuniformity acceptable.

    - David.Thompson1 at worldnet.att.net
     
    Dave Thompson, Apr 4, 2005
    #14
  15. Michael B Allen

    CBFalconer Guest

    Dave Thompson wrote:
    > On 26 Mar 2005 16:50:31 -0800, wrote:
    >> Rouben Rostamian wrote:

    > <snip>
    >>> return min + (int)((max-min+1.0)*rand()/(1.0+RAND_MAX));

    > <snip>
    >> This solution (which, unfortunately, is endorsed by the comp.lang.c
    >> FAQ) is no better. As others have posted, you're up against the
    >> pigeon-hole principle, you can't fix it by just changing the
    >> mapping in some way.
    >>
    >> And its a real problem in practice -- RAND_MAX need not be higher
    >> than 65535, and in most of the compilers on the most popular
    >> platform it is indeed exactly this. I have a more complete

    > summary of the issue here:
    >>
    >> http://www.pobox.com/~qed/random.html

    >
    > Need not be higher than, and often is, 32767 (= minimum INT_MAX).
    >
    > Although for a desired choice range of no more than about 30, I
    > might consider the <.1% nonuniformity acceptable.


    AFAIK there is no specification for RAND_MIN, which will be at
    least 1 for many implementations. If you require specific
    characteristics the only answer is to supply your own random
    implmentation. Even then you need to be aware of what is and is
    not guaranteed. For example, 32 bit ints are not guaranteed,
    contrary to Hsiehs (websnarf) hidden assumptions in at least some
    of his code.

    --
    "If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers." - Keith Thompson
     
    CBFalconer, Apr 4, 2005
    #15
  16. CBFalconer <> writes:
    [...]
    > AFAIK there is no specification for RAND_MIN, which will be at
    > least 1 for many implementations.

    [...]

    There is no RAND_MIN. The standard says that rand() "computes a
    sequence of pseudo-random integers in the range 0 to RAND_MAX".

    If an implementation's rand() function never returns 0, the implementation
    is either non-conforming or of poor quality.

    Do you know of an implementation in which rand() never returns 0?

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
     
    Keith Thompson, Apr 4, 2005
    #16
  17. Michael B Allen

    CBFalconer Guest

    Keith Thompson wrote:
    > CBFalconer <> writes:
    > [...]
    >> AFAIK there is no specification for RAND_MIN, which will be at
    >> least 1 for many implementations.

    > [...]
    >
    > There is no RAND_MIN. The standard says that rand() "computes a
    > sequence of pseudo-random integers in the range 0 to RAND_MAX".
    >
    > If an implementation's rand() function never returns 0, the
    > implementation is either non-conforming or of poor quality.
    >
    > Do you know of an implementation in which rand() never returns 0?


    Yes. Any Linear Congruential with a zero adder. Any CRC based
    system.

    --
    "If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers." - Keith Thompson
     
    CBFalconer, Apr 4, 2005
    #17
  18. Michael B Allen

    Eric Sosman Guest

    Keith Thompson wrote:

    > CBFalconer <> writes:
    > [...]
    >
    >>AFAIK there is no specification for RAND_MIN, which will be at
    >>least 1 for many implementations.

    >
    > [...]
    >
    > There is no RAND_MIN. The standard says that rand() "computes a
    > sequence of pseudo-random integers in the range 0 to RAND_MAX".
    >
    > If an implementation's rand() function never returns 0, the implementation
    > is either non-conforming or of poor quality.
    >
    > Do you know of an implementation in which rand() never returns 0?


    The trouble is in the testing: If you sample three
    hundred twenty-seven quadrillion rand() values and see
    no zeroes, can you conclude that rand() will never, ever,
    under any circumstances return a zero?

    It's reminiscent of the demonstration that all crows are
    black. You can travel the world observing crows and noting
    that all seen are black; with each successive black crow your
    confidence in the hypothesis increases. But "all crows are
    black" is equivalent to "all non-black things are non-crows,"
    so there's a less strenuous way to proceed: Just sit in your
    armchair (none of that tedious travelling), cast your eyes
    about you, and observe non-black objects in your field of view.
    Behold the butterknife: a non-black non-crow that raises your
    confidence. Behold the white cover of K&R, another non-crow:
    your confidence swells as if certain spammed pharmaceuticals
    had been used. Behold the pinkish appurtenances of the image
    of Miss Download, overtly mammalian and hence not a crow: you
    are ready to submit your thesis to a journal (and stop thinking
    about that swelling, okay?). The upshot is that you can raise
    your confidence in "all crows are black" without every observing
    a single crow ...

    --
    Eric Sosman
    lid
     
    Eric Sosman, Apr 5, 2005
    #18
  19. CBFalconer <> writes:
    > Keith Thompson wrote:
    >> CBFalconer <> writes:
    >> [...]
    >>> AFAIK there is no specification for RAND_MIN, which will be at
    >>> least 1 for many implementations.

    >> [...]
    >>
    >> There is no RAND_MIN. The standard says that rand() "computes a
    >> sequence of pseudo-random integers in the range 0 to RAND_MAX".
    >>
    >> If an implementation's rand() function never returns 0, the
    >> implementation is either non-conforming or of poor quality.
    >>
    >> Do you know of an implementation in which rand() never returns 0?

    >
    > Yes. Any Linear Congruential with a zero adder. Any CRC based
    > system.


    Do you know of a specific C library implementation that uses an
    algorithm in which rand() never returns 0?

    Even the sample implementation in the standard (which isn't very good)
    returns 0 every few thousand iterations.

    As long as the internal state is bigger than the values returned,
    you'll probably get 0 every now and then.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
     
    Keith Thompson, Apr 5, 2005
    #19
  20. Michael B Allen

    CBFalconer Guest

    Eric Sosman wrote:
    > Keith Thompson wrote:
    >> CBFalconer <> writes:
    >> [...]
    >>
    >>> AFAIK there is no specification for RAND_MIN, which will be at
    >>> least 1 for many implementations.

    >>
    >> [...]
    >>
    >> There is no RAND_MIN. The standard says that rand() "computes a
    >> sequence of pseudo-random integers in the range 0 to RAND_MAX".
    >>
    >> If an implementation's rand() function never returns 0, the implementation
    >> is either non-conforming or of poor quality.
    >>
    >> Do you know of an implementation in which rand() never returns 0?

    >
    > The trouble is in the testing: If you sample three
    > hundred twenty-seven quadrillion rand() values and see
    > no zeroes, can you conclude that rand() will never, ever,
    > under any circumstances return a zero?


    I am thinking of cases where the generation method is known, and
    thus the lack of a zero can be guaranteed.

    >
    > It's reminiscent of the demonstration that all crows are
    > black. You can travel the world observing crows and noting
    > that all seen are black; with each successive black crow your
    > confidence in the hypothesis increases. But "all crows are


    Nah, it just confirms that all crows have a black side, which they
    normally present to you.

    --
    "If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers." - Keith Thompson
     
    CBFalconer, Apr 5, 2005
    #20
    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. Buddy Ackerman

    999 error

    Buddy Ackerman, Mar 3, 2006, in forum: ASP .Net
    Replies:
    3
    Views:
    3,460
    David Wang [Msft]
    Mar 4, 2006
  2. Elmar Baumann
    Replies:
    0
    Views:
    638
    Elmar Baumann
    Feb 2, 2004
  3. I_have_nothing

    Any easy to printf an interger in 9,999, 99 format?

    I_have_nothing, May 13, 2005, in forum: C Programming
    Replies:
    4
    Views:
    428
    Chris McDonald
    May 13, 2005
  4. HAPPY NEW YEAR Funny Christmas wallpapers, theme F

    Funny Christmas wallpapers, theme & 15,999$/- per day

    HAPPY NEW YEAR Funny Christmas wallpapers, theme F, Dec 26, 2008, in forum: C Programming
    Replies:
    0
    Views:
    315
    HAPPY NEW YEAR Funny Christmas wallpapers, theme F
    Dec 26, 2008
  5. Armin Gajda

    Regular Expression for 001-999

    Armin Gajda, Feb 7, 2006, in forum: Perl Misc
    Replies:
    13
    Views:
    927
    William James
    Feb 7, 2006
Loading...

Share This Page