A portable random number generator well suited for the rejection method

ABSTRACT

Up to now, all known efficient portable implementations of linear congruential random number generators with modulus 231 – 1 have worked only 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 generator with small multiplier. A method is described that works for any multiplier smaller than 230. It uses the decomposition of multiplier 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 modulo 221 – 1. Coded in ANSI-C and FORTRAN77 the method results in a portable implementation of the linear congruential generator that is as fast or faster than other portable methods.

REFERENCES

• 1: AFFLERBACH, L., AND HORMANN, W. 1992. Nonuniform random numbers: a sensitivity analysis for transformation methods. In International Workshop on Computat~onally Intenswe Methods ~n Simulation and Optimization, Springer-Verlag, Berlin. U. Dieter and G. Ch. Pfiug, Ed., Lecture Notes in Econom. Math. Systems 374, 135-144.
• 2: Paul Bratley , Bennett L Fox , Linus E Schrage, A guide to simulation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1986
• 3: George A Fishman , Louis R Moore, III, An exhaustive analysis of multiplicative congruential random number generators with modulus 2³¹-1, SIAM Journal on Scientific and Statistical Computing, v.7 n.1, p.24-45, Jan. 1986 [doi>10.1137/0907002]
• 4: GROTHE, H. 1987. Matrix generators for pseudo-random vector generation. Stattstical Papers 28, 233 238.
• 5: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 6: P. L'Ecuyer, Efficient and portable combined random number generators, Communications of the ACM, v.31 n.6, p.742-751, June 1988 [doi>10.1145/62959.62969]
• 7: Pierre L'Ecuyer, Random numbers for simulation, Communications of the ACM, v.33 n.10, p.85-97, Oct. 1990 [doi>10.1145/84537.84555]
• 8: MARSE, K., AND ROBERTS, S. D. 1983. Implementing a portable Fortran uniform (0, 1) generator. Simulation 41, 4 (Oct.), 135-139.
• 9: S. K. Park , K. W. Miller, Random number generators: good ones are hard to find, Communications of the ACM, v.31 n.10, p.1192-1201, Oct. 1988 [doi>10.1145/63039.63042]
• 10: W. H. Payne , J. R. Rabung , T. P. Bogyo, Coding the Lehmer pseudo-random number generator, Communications of the ACM, v.12 n.2, p.85-86, Feb. 1969 [doi>10.1145/362848.362860]
• 11: Linus Schrage, A More Portable Fortran Random Number Generator, ACM Transactions on Mathematical Software (TOMS), v.5 n.2, p.132-138, June 1979 [doi>10.1145/355826.355828]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

General Terms:
Algorithms

Keywords:
linear congruential generator, portability, quality of nonuniform random numbers, rejection method, uniform random number generator