Generating a uniform distribution of INTEGERS in C

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.

On some implementations, rand() did not provide good randomness on its lower order bits, so the modulus operator would not provide very random results. If you find that to be the case, you could try this instead:

int uniform_distribution(int rangeLow, int rangeHigh) {
    double myRand = rand()/(1.0 + RAND_MAX); 
    int range = rangeHigh - rangeLow + 1;
    int myRand_scaled = (myRand * range) + rangeLow;
    return myRand_scaled;
}

Using rand() this way will produce a bias as noted by Lior. But, the technique is fine if you can find a uniform number generator to calculate myRand. One possible candidate would be drand48(). This will greatly reduce the amount of bias to something that would be very difficult to detect.

However, if you need something cryptographically secure, you should use an algorithm outlined in Lior's answer, assuming your rand() is itself cryptographically secure (the default one is probably not, so you would need to find one). Below is a simplified implementation of what Lior described. Instead of counting bits, we assume the range falls within RAND_MAX, and compute a suitable multiple. Worst case, the algorithm ends up calling the random number generator twice on average per request for a number in the range.

int uniform_distribution_secure(int rangeLow, int rangeHigh) {
    int range = rangeHigh - rangeLow + 1;
    int secureMax = RAND_MAX - RAND_MAX % range;
    int x;
    do x = secure_rand(); while (x >= secureMax);
    return rangeLow + x % range;
}