c - Generate a random number within range?

Question

This question already has answers here:

Answer 1

This is actually a bit harder to get really correct than most people realize:

int rand_lim(int limit) {
/* return a random number between 0 and limit inclusive.
 */

    int divisor = RAND_MAX/(limit+1);
    int retval;

    do { 
        retval = rand() / divisor;
    } while (retval > limit);

    return retval;
}

Attempts that just use % (or, equivalently, /) to get the numbers in a range almost inevitably introduce skew (i.e., some numbers will be generated more often than others).

As to why using % produces skewed results: unless the range you want is a divisor of RAND_MAX, skew is inevitable. If you start with small numbers, it's pretty easy to see why. Consider taking 10 pieces of candy (that we'll assume you can't cut, break, etc. into smaller pieces) and trying to divide it evenly between three children. Clearly it can't be done--if you hand out all the candy, the closest you can get is for two kids to get three pieces of candy, and one of them getting four.

There's only one way for all the kids to get the same number of pieces of candy: make sure you don't hand out the last piece of candy at all.

To relate this to the code above, let's start by numbering the candies from 1 to 10 and the kids from 1 to 3. The initial division says since there are three kids, our divisor is three. We then pull a random candy from the bucket, look at its number and divide by three and hand it to that kid -- but if the result is greater than 3 (i.e. we've picked out candy number 10) we just don't hand it out at all -- we discard it and pick out another candy.

Of course, if you're using a modern implementation of C++ (i.e., one that supports C++11 or newer), you should usually use one the distribution classes from the standard library. The code above corresponds most closely with std::uniform_int_distribution, but the standard library also includes uniform_real_distribution as well as classes for a number of non-uniform distributions (Bernoulli, Poisson, normal, maybe a couple others I don't remember at the moment).