Truly random numbers are often hard to come by. Most operating systems carefully gather randomness from here and there, store it in an “entropy pool”, and dish it out as needed to various processes. Generally this is in binary form, e.g. the Unix-type systems’ /dev/random which provides random bytes.
Often times you may need a random integers between 0 and some particular number, m. For example, you may need to generate a random password of upper and lower case letters and numbers: you need some integers between 0 and 62: 0 ≤ v < 62. So how can you effeciently extract non-binary numbers from a random bit stream?
Unable to find any existing routines for this, I developed this perl module: Ran_Int.pm. The core idea behind the four routines in this module is as follows:
It is quite likely though that the pool size, r, will not be divisible by m. In that case we find the largest integer, r', less than r that’s divisible by m and discard our pool if it is greater than or equal to r'. As long as r is much larger than m: the pool size is much larger than the size of integers we are extracting from it, discards will be infrequent.
The four routines all do the same thing, but with minor differences. “A” and “D” return v/d. “B” and “C” return v mod m. “A” and “B” insert randomness on the right, whereas “C” and “D” insert randomness on the left.
Last modified: December 28, 2015