Quickly and safely determine random number within range

How would I quickly and safely* determine a random number within a range of 0 (inclusive) to r (exclusive)?

In other words, an optimized version of rejection sampling:

u32 myrand(u32 x)
{
    u32 ret = rand();

    while(ret >= x)
        ret = rand();

    return(ret);
}

*By safely, I mean a uniform di开发者_StackOverflow社区stribution.

---

Rejection sampling is the way to go if you want to have a uniform distribution on the result. It is notoriously difficult to do anything smarter. Using the modulo operator for instance results in an uneven distribution of the result values for any number that's not a power of 2.

The algorithm in you post however can be improved by discarding the unnecessary most significant bits. (See below.)

This is how the standard Java API implements Random.nextInt(int n):

public int nextInt(int n) {

    [...]

    if ((n & -n) == n)  // i.e., n is a power of 2
        return (int)((n * (long)next(31)) >> 31);

    int bits, val;
    do {
        bits = next(31);
        val = bits % n;
    } while (bits - val + (n-1) < 0);

    return val;
}

And in the commens you can read:

The algorithm is slightly tricky. It rejects values that would result in an uneven distribution (due to the fact that 2³¹ is not divisible by n). The probability of a value being rejected depends on n. The worst case is n=2³⁰+1, for which the probability of a reject is 1/2, and the expected number of iterations before the loop terminates is 2.

---

u32 myrand(u32 x)
{
    return rand() % (x+1);
}

Since the question has been changed to include even distribution, this would need something more like this:

u32 myrand(u32 x)
{
   assert(x <= RAND_MAX && x > 0);
   int numOfRanges = (RAND_MAX % x);
   int maxAcceptedRand = numOfRanges * x;
   int randNumber;
   do
   {
      randNumber = rand();
   }
   while(randNumber <= maxAcceptedRand);
   return number / numOfRanges;
}