Bit-parallel random number generation for discrete uniform distributions Original Research Article

When a die is cast, the outcome is one of the six sides, i.e. the outcome is discrete and uniformly distributed over the range R={1,2,3,4,5,6}. Generating random numbers with such a distribution is very easy: obtain a random number w∈W, the domain of the random numbers, and take (w mod |R|)+1. However, many uniform discrete distributions have a rather short range, e.g., |R|=6 in a dice game, and |R|=3 for the walking directions of a 2-dimensional nonreversal random walk. The number w is typically a machine word, i.e. log2(|W|)≈32 in a 32-bit computer, so generating a log2(|R|)-bit random number has consumed about 32 random bits. When |W|⪢|R|, it is wasteful and hence inefficient. This paper presents an efficient algorithm for generating random numbers for the distributions with |R| discrete uniform outcomes. The algorithm uses parallel bit-wise operations on machine words. The performance results of the algorithm are presented. The statistical quality of the random numbers generated from this algorithm is also discussed.