Generating a uniform distribution of INTEGERS in C

c algorithm statistics integer uniform
solvingPuzzles picture solvingPuzzles · Jul 25, 2012 · Viewed 21k times · Source

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

Lior Kogan picture Lior Kogan · Jul 25, 2012

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.

Related questions

Rolling median algorithm in C

I am currently working on an algorithm to implement a rolling median filter (analogous to a rolling mean filter) in C. From my search of the literature, there appear to be two reasonably efficient ways to do it. The first …

Read More
Printing prime numbers from 1 through 100

This c++ code prints out the following prime numbers: 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97. But I don't think that's the way my book wants it to be written. It mentions something about square root of a number. So I did try changing my 2nd loop …

Read More
How to reverse a singly linked list using only two pointers?

I wonder if there exists some logic to reverse a singly-linked list using only two pointers. The following is used to reverse the single linked list using three pointers namely p, q, r: struct node { int data; struct node *link; }; …

Read More