Generating a uniform distribution of INTEGERS in C

by

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.

More Related Contents:

  1. Rolling median algorithm in C
  2. Recursive and non-recursive traversal of three degree tree
  3. how to show time performance for merge sort? [closed]
  4. Why this C code makes infinite loop?
  5. Assignment makes pointer from integer without a cast and vice versa in c
  6. Efficient Algorithm for Bit Reversal (from MSB->LSB to LSB->MSB) in C
  7. What integer hash function are good that accepts an integer hash key?
  8. How to reverse a singly linked list using only two pointers?
  9. Check if input is integer type in C
  10. Unique random number generation in an integer array [duplicate]
  11. Calculating factorial of large numbers in C
  12. How do I check if an integer is even or odd? [closed]
  13. How to convert integer to string in C? [duplicate]
  14. Combine Gyroscope and Accelerometer Data
  15. Question about C behaviour for unsigned integer underflow
  16. Power by squaring for negative exponents
  17. C programming, why does this large array declaration produce a segmentation fault?
  18. Traverse Matrix in Diagonal strips
  19. Program to print permutations of given elements [closed]
  20. Gaussian elimination without result for acceleration
  21. Fastest way to calculate a 128-bit integer modulo a 64-bit integer
  22. Find maximum of three number in C without using conditional statement and ternary operator
  23. Algorithm to find all the exact divisors of a given integer
  24. Why is 248×248 the maximum bi dimensional array size I can declare?
  25. What happens when I assign long int to int in C?
  26. Which is better way to calculate nCr
  27. Merging two sorted linked lists
  28. a working non-recursive floodfill algorithm written in C?
  29. Algorithm to pick values from array that sum closest to a target value?
  30. Avoid Overflow when Calculating π by Evaluating a Series Using 16-bit Arithmetic?

Leave a Comment