A fast normal random number generator

ABSTRACT

A method is presented for generating pseudorandom numbers with a normal distribution. The technique uses the ratio of uniform deviates method discovered by Kinderman and Monahan with an improved set of bounding curves. An optimized quadratic fit reduces the expected number of logarithm evaluations to 0.012 per normal deviate. The method gives a theoretically correct distribution and can be implemented in 15 lines of FORTRAN. Timing and source size comparisons are made with other methods for generating normal deviates. The proposed algorithm compares favorably with some of the better algorithms.

REFERENCES

• 1: J. H. Ahrens , U. Dieter, Computer methods for sampling from the exponential and normal distributions, Communications of the ACM, v.15 n.10, p.873-882, Oct. 1972 [doi>10.1145/355604.361593]
• 2: Richard P. Brent, Algorithm 488: A Gaussian pseudo-random number generator, Communications of the ACM, v.17 n.12, p.704-706, Dec 1974 [doi>10.1145/361604.361629]
• 3: P. Griffiths , I. D. Hill, Applied statistics algorithms, John Wiley & Sons, Inc., New York, NY, 1985
• 4: A. J. Kinderman , J. F. Monahan, Computer Generation of Random Variables Using the Ratio of Uniform Deviates, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.257-260, Sept. 1977 [doi>10.1145/355744.355750]
• 5: K~UTtt, D. E. The Art of Computer Programming, 2nd ed., Vol. 2: Seminumerical Algorithms. Addison-Wesley, Reading, Mass., 1981, 114 127.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

General Terms:
Algorithms, Performance, Theory

Keywords:
Gaussian distribution, normal distribution, pseudorandom numbers, random numbers, ratio of uniform deviates