ALGORITHM 488: A GAUSSIAN PSEUDO-RANDOM NUMBER GENERATOR [G5]

RICHARD P. BRENT

Abstract

We present an algorithm GRAND for generating normally distributed pseudo-random numbers, assuming the existence of a source of uniform random numbers. The method is exact, apart from the effect of rounding errors. The idea of using a rejection technique to avoid any elementary function evaluations is due to Von Neumann [4] and Forsythe [3], but our implementation requires less uniform samples per result than previous implementations. In fact, only about 1.38 uniform samples are required per normal variate.

Comments

Only the Abstract is given here. The algorithm appeared as [1]. It is still considered one of the fastest algorithms for generating normal random variates on sequential computers. Other methods are preferable on vector processors [2].

References

1. R. P. Brent, “Algorithm 488: A Gaussian pseudo-random number generator [G5]”, Communications of the ACM 17 (1974), 704–706. Zbl 292.65003. rpb023.

2. R. P. Brent, Fast Normal Random Number Generators for Vector Processors, Technical Report TR-CS-93-04, Computer Sciences Laboratory, Australian National University, March 1993, 7 pp. rpb141.

3. G. E. Forsythe, “Von Neumann’s comparison method for sampling from the normal and other distributions”, Mathematics of Computation 26 (1972), 817–826.

4. J. Von Neumann, “Various techniques used in connection with random digits”, in Collected Works, Vol. 5, Pergamon Press, New York, 1963, 768–770.

Computer Centre, Australian National University, Canberra, Australia

1991 Mathematics Subject Classification. Primary 65C10; Secondary 65C05.

Key words and phrases. Random numbers, pseudo-random numbers, Gaussian distribution, normal distribution, Von Neumann and Forsythe method, rejection method.

CR Categories. 5.39, 5.5.

Language. Fortran.

Received 9 November 1973, and 19 December 1973.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1974, ACM, Inc. General permission to republish, but not for profit, all or pat of this material is granted, provided that ACM’s copyright notice is given and that reference is made to the publication, to its date of issue, and to the fact that reprinting privileges were granted by permission of the Association for Computing Machinery.

Abstract and Comments copyright \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent.

rpb023a typeset using AMS-L^{A}TEX