algorithm - Generating a uniform distribution of INTEGERS in C

Question

I've written a C function that I think selects integers from a uniform distribution with range [rangeLow, rangeHigh], inclusive. This isn't homework--I'm just using this in some embedded systems tinkering that I'm doing for fun.

In my test cases, this code appears to produce an appropriate distribution. I'm not feeling fully confident that the implementation is correct, though. Could someone do a sanity check and let me know if I've done anything wrong here?

//uniform_distribution returns an INTEGER in [rangeLow, rangeHigh], inclusive.
int uniform_distribution(int rangeLow, int rangeHigh)
{
    int myRand = (int)rand(); 
    int range = rangeHigh - rangeLow + 1; //+1 makes it [rangeLow, rangeHigh], inclusive.
    int myRand_scaled = (myRand % range) + rangeLow;
    return myRand_scaled;
}
//note: make sure rand() was already initialized using srand()

P.S. I searched for other questions like this. However, it was hard to filter out the small subset of questions that discuss random integers instead of random floating-point numbers.

Answer 1

Let's assume that rand() generates a uniformly-distributed value I in the range [0..RAND_MAX], and you want to generate a uniformly-distributed value O in the range [L,H].

Suppose I in is the range [0..32767] and O is in the range [0..2].

According to your suggested method, O= I%3. Note that in the given range, there are 10923 numbers for which I%3=0, 10923 number for which I%3=1, but only 10922 number for which I%3=2. Hence your method will not map a value from I into O uniformly.

As another example, suppose O is in the range [0..32766].

According to your suggested method, O=I%32767. Now you'll get O=0 for both I=0 and I=32767. Hence 0 is twice as likely than any other value - your method is again nonuniform.

---

The suggest way to generate a uniform mapping is as follow:

1. Calculate the number of bits that are needed to store a random value in the range [L,H]:

   unsigned int nRange = (unsigned int)H - (unsigned int)L + 1;
   unsigned int nRangeBits= (unsigned int)ceil(log((double(nRange) / log(2.));

2. Generate nRangeBits random bits

   this can be easily implemented by shifting-right the result of rand()

3. Ensure that the generated number is not greater than H-L. If it is - repeat step 2.

4. Now you can map the generated number into O just by adding a L.