Random Integers from Random Integers

Or “Smaller Random Integers from Larger”. This topic is easy to overlook. It is also easy to implement badly.

One may have the best basic random number generator and yet have serious problems doing something with its result that looks easy. That “easy something” is the task of using the basic generator to produce random numbers in some other range.

In this discussion we assume that the basic generator has a larger range than the desired range. For example our base generator may return numbers in the range of 0 to 65535 yet we desire numbers in the range of 0 to 9. Using these numbers two obvious methods look like...

Method 1: Result = rand( ) % 10
Method 2: Result = int(rand( )*10/65536)

Both are wrong. Not by much, but still wrong. To show the problem assume that rand() returns number in the range of 0 to 7 and that we want a result in the range of 0 to 2.
 

In each case, result=2 is underrepresented. A little thought will show that the mapping of any rand() with a range equal to some power of two in length into any range not a power of 2 in length will lead to this problem.

What to do. First be very careful about any use of method one. The basic Linear Congrential Generator has a serious flaw when its divisor is a power of 2 (often the case) and if the entire seed is returned. Method one could end up using only the low order “bad bits” of seed.

Use method two. Then think of the bits returned from rand() as being a binary fraction with the binary point on the left. Multiply by the result range. The integer portion of the product (the bits to the left of the binary point in the product) is often the desired result. Now ask “if I had all 1 bits to the right of the original rand() would the result change?” If the concatenation of hundreds of 1 bits to the original rand() could not change the integer portion of the product then we are done. Return the value to the left of the binary point. But if a mess of 1 bits could change the result then we have to get another rand() and figure it into the product. If in doing so the product carries into the integer portion of the original product then return that new integer portion. If not then repeat until either another rand() is shown to have no effect or it causes a carry into the original integer portion. Sounds hard. It aint.

To make the above a little simpler, first special case requested ranges equal to some power of 2. If the underlying generator allows, these specific values can be processed by simply masking rand() to the proper size. After these ranges are excluded, the test for possible overflow can be made by adding the range to the low bits of the product. This has the same effect as originally obtaining rand()+1. If that addition does not carry past the binary point then no amount of 1 bits can either.

All of the above is about 20 lines of 80x86 assembly code.

One other hint: use a simple rejection method for requested ranges above 70% of the range of the low level generator. In a C-like pseudo code our function overview becomes...

unsigned int randRange(unsigned int maxValue)
{
  unsigned int range = maxValue+1;
  if ((maxValue & range) == 0)
  return rand() & maxValue; //mask and be done
  if (maxValue > 40000)
  {
    unsigned int temp;
    do temp=rand() until (temp < range;); // rejection method
    return temp;
}
//
// return result from the 20 lines of assembly code
//
}

Next Topic (Short Sequence Generator)
Previous Topic
Return to index