A PORTABLE RANDOM NUMBER GENERATOR WELL SUITED FOR THE REJECTION METHOD

Up to now, all known efficient portable implementations of linear cong ruential random number generators with modulus 2(31) - 1 have worked o nly with multipliers that are small compared with the modulus. We show that for nonuniform distributions, the rejection method may generate random numbers of bad qualify if combined with a linear congruential g enerator with small multiplier. A method is described that works for a ny multiplier smaller than 2(30). It uses the decomposition of multipl ier and seed in high-order and low-order bits to compute the upper and lower half of the product. The sum of the two halfs gives the product of multiplier and seed module 2(31) - 1. Coded in ANSI-C and Fortran7 7 the method results in a portable implementation of the linear congru ential generator that is as fast or faster than other portable methods .