Decomposition with simulated division for efficiently generating random numbers

Most portable implementations of the prime modulus multiplicative congruential random number (RN) generator have restrictions on the multiplier. The decomposition method which decomposes a multiplier into a = a₀ + a₁2 ^{b 2 - 1} + a₂2^{b - 2}, where b is the size of the computer word, on the other hand, is applicable to all multipliers. With the special structure of the decomposition, the technique of simulated division is considered in this paper to facilitate the computation for RN generators with modulus 2³¹ - 1. Some empirical speed comparisons reveal that the reduction in the execution time is around 1 4 to 1 3 for various computers.