Gaussian random number generators

ABSTRACT

Rapid generation of high quality Gaussian random numbers is a key capability for simulations across a wide range of disciplines. Advances in computing have brought the power to conduct simulations with very large numbers of random numbers and with it, the challenge of meeting increasingly stringent requirements on the quality of Gaussian random number generators (GRNG). This article describes the algorithms underlying various GRNGs, compares their computational requirements, and examines the quality of the random numbers with emphasis on the behaviour in the tail region of the Gaussian probability density function.

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: Joachim H. Ahrens , Ulrich Dieter, Efficient table-free sampling methods for the exponential, Cauchy, and normal distributions, Communications of the ACM, v.31 n.11, p.1330-1337, Nov. 1988 [doi>10.1145/50087.50094]
• 3: Andraka, R. and Phelps, R. 1998. An FPGA based processor yields a real time high fidelity radar environment simulator. In Military and Aerospace Applications of Programmable Devices and Technologies Conference.
• 4: James R. Bell, Algorithm 334: Normal random deviates, Communications of the ACM, v.11 n.7, p.498, July 1968 [doi>10.1145/363397.363547]
• 5: Emmanuel Boutillon , Jean-Luc Danger , Adel Ghazel, Design of High Speed AWGN Communication Channel Emulator, Analog Integrated Circuits and Signal Processing, v.34 n.2, p.133-142, February 2003 [doi>10.1023/A:1021937002981]
• 6: Box, G. E. P. and Muller, M. E. 1958a. A note on the generation of random normal deviates. Annals Math. Stat. 29, 610--611.
• 7: Box, G. E. P. and Muller, M. E. 1958b. A note on the generation of random normal deviates. Annals Math. Stat. 29, 2, 610--611.
• 8: 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]
• 9: Brent, R. P. 1993. Fast normal random number generators on vector processors. Tech. Rep. TR-CS-93-04, Department of Computer Science, The Australian National University, Canberra 0200 ACT, Australia.
• 10: Brent, R. P. 1997. A fast vectorised implementation of Wallace's normal random number generator. Tech. Rep. TR-CS-97-07, Department of Computer Science, The Australian National University, Canberra 0200 ACT, Australia.
• 11: Brent, R. P. 2003. Some comments on C. S. Wallace's random number generators. Comput. J., to appear.
• 12: Chen, J., Moon, J., and Bazargan, K. 2004. Reconfigurable readback-signal generator based on a field-programmable gate array. IEEE Trans. Magn. 40, 3, 1744--1750.
• 13: Winnie Chen , Roger L. Burford, Quality evaluation of some combinations of unit uniform random number generators and unit normal transformation algorithms, Proceedings of the 14th annual symposium on Simulation, p.129-149, March 17-20, 1981, Tampa, Florida, United States
• 14: Danger, J.-L., Ghazel, A., Boutillon, E., and Laamari, H. 2000. Efficient FPGA implementation of Gaussian noise generator for communication channel emulation. In ICECS'2000. IEEE, Jounieh, Lebanon.
• 15: Devroye, L. 1986. Non-Uniform Random Variate Generation. Springer-Verlag, http://cg.scs.carleton.ca/~luc/rnbookindex.html, New York.
• 16: Forsythe, G. E. 1972. Von Neumann's comparison method for random sampling from the normal and other distributions. Math. Computation 26, 120, 817--826.
• 17: Gebhardt, F. 1964. Generating normally distributed random numbers by inverting the normal distribution function. Math. Computation 18, 86, 302--306.
• 18: Wolfgang Hörmann, A note on the quality of random variates generated by the ratio of uniforms method, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.4 n.1, p.96-106, Jan. 1994 [doi>10.1145/174619.174623]
• 19: Kabal, P. 2000. Generating Gaussian pseudo-random deviates. Tech. Rep., Department of Electrical and Computer Engineering, McGill University.
• 20: 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]
• 21: R. Knop, Remark on algorithm 334 [G5]: normal random deviates, Communications of the ACM, v.12 n.5, p.281, May 1969 [doi>10.1145/362946.362996]
• 22: Knuth, D. E. 1981. Seminumerical Algorithms, Second ed. The Art of Computer Programming, vol. 2. Addison-Wesley, Reading, Massachusetts.
• 23: Richard Kronmal, Evaluation of a Pseudorandom Normal Number Generator, Journal of the ACM (JACM), v.11 n.3, p.357-363, July 1964 [doi>10.1145/321229.321238]
• 24: Pierre L'Ecuyer, Testing random number generators, Proceedings of the 24th conference on Winter simulation, p.305-313, December 13-16, 1992, Arlington, Virginia, United States [doi>10.1145/167293.167354]
• 25: Pierre L'Ecuyer, Maximally equidistributed combined Tausworthe generators, Mathematics of Computation, v.65 n.213, p.203-213, Jan. 1996 [doi>10.1090/S0025-5718-96-00696-5]
• 26: Pierre L'Ecuyer, Software for uniform random number generation: distinguishing the good and the bad, Proceedings of the 33nd conference on Winter simulation, December 09-12, 2001, Arlington, Virginia
• 27: L'Ecuyer, P. and Simard, R. 2005. TestU01. http://www.iro.umontreal.ca/~simardr/indexe.html.
• 28: Dong-U Lee , Wayne Luk , John D. Villasenor , Peter Y. K. Cheung, A Gaussian Noise Generator for Hardware-Based Simulations, IEEE Transactions on Computers, v.53 n.12, p.1523-1534, December 2004 [doi>10.1109/TC.2004.106]
• 29: Lehmer, D. H. 1949. Mathematical methods in large-scale computing units. In Proceedings of the 2nd Symposium on Large-Scale Digital Calculating Machinery. Harvard University Press, Cambridge, Massachusetts, 141--146.
• 30: Joseph L. Leva, Algorithm 712: A normal random number generator, ACM Transactions on Mathematical Software (TOMS), v.18 n.4, p.454-455, Dec. 1992 [doi>10.1145/138351.138367]
• 31: Joseph L. Leva, A fast normal random number generator, ACM Transactions on Mathematical Software (TOMS), v.18 n.4, p.449-453, Dec. 1992 [doi>10.1145/138351.138364]
• 32: Marsaglia, G. 1964. Generating a variable from the tail of the normal distribution. Technometrics 6, 101--102.
• 33: Marsaglia, G. 1997. The Diehard random number test suite. http://stat.fsu.edu/pub/diehard/.
• 34: Marsaglia, G. 2004. Evaluating the normal distribution. J. Statis. Softw. 11, 4, 1--11.
• 35: Marsaglia, G. and Bray, T. A. 1964. A convenient method for generating normal variables. SIAM Rev. 6, 3, 260--264.
• 36: G. Marsaglia , M. D. MacLaren , T. A. Bray, A fast procedure for generating normal random variables, Communications of the ACM, v.7 n.1, p.4-10, Jan. 1964 [doi>10.1145/363872.363883]
• 37: Marsaglia, G. and Tsang, W. W. 1984a. A fast, easily implemented method for sampling from decreasing or symmetric unimodal density functions. SIAM J. Sci. Statis. Comput. 5, 349--359.
• 38: Marsaglia, G. and Tsang, W. W. 1984b. A fast, easily implemented method for sampling from decreasing or symmetric unimodal density functions. SIAM J. Sci. Stat. Comput. 5, 2 (June), 349--359.
• 39: George Marsaglia , Wai Wan Tsang, The Monty Python method for generating random variables, ACM Transactions on Mathematical Software (TOMS), v.24 n.3, p.341-350, Sept. 1998 [doi>10.1145/292395.292453]
• 40: Marsaglia, G. and Tsang, W. W. 2000. The ziggurat method for generating random variables. J. Statis. Softw. 5, 8, 1--7.
• 41: Makoto Matsumoto , Takuji Nishimura, Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.1, p.3-30, Jan. 1998 [doi>10.1145/272991.272995]
• 42: McCollum, J. M., Lancaster, J. M., Bouldin, D. W., and Peterson, G. D. 2003. Hardware acceleration of pseudo-random number generation for simulation applications. In IEEE Southeastern Symposium on System Theory. IEEE, Morgantown, WV.
• 43: Moler, C. 1995. Random thoughts: 10⁴³⁵ years is a very long time. http://www.mathworks.com/company/newsletters/news_notes/pdf/Cleve.pdf.
• 44: Moler, C. B. 2004. Numerical Computing in Matlab. Society for Industrial and Applied Mathematics, USA.
• 45: John W. Dalle Molle , Melvin J. Hinich , Douglas J. Morrice, Higher-order cumulant spectral-based statistical tests of pseudo-random variate generators, Proceedings of the 24th conference on Winter simulation, p.618-625, December 13-16, 1992, Arlington, Virginia, United States [doi>10.1145/167293.167648]
• 46: Muller, M. E. 1958. An inverse method for the generation of random normal deviates on large-scale computers. Mathematical Tables and Other Aids to Computation 12, 63, 167--174.
• 47: Mervin E. Muller, A Comparison of Methods for Generating Normal Deviates on Digital Computers, Journal of the ACM (JACM), v.6 n.3, p.376-383, July 1959 [doi>10.1145/320986.320992]
• 48: M. C. Pike, Algorithm 267: random normal deviate [G5], Communications of the ACM, v.8 n.10, p.606, Oct. 1965 [doi>10.1145/365628.365649]
• 49: Press, W. H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. P. 1997. Numerical Recipes in C, Second ed. Cambridge University Press, Cambridge.
• 50: Rukhin, A., Soto, J., Nechvatal, J., Smid, M., Barker, E., Leigh, S., Levenson, M., Vangel, M., Banks, D., Heckert, A., Dray, J., and Vo, S. 2001. A statistical test suite for random and pseudorandom number generators for cryptographic applications. NIST special publication 800-22, National Institute of Standards and Technology (NIST), Gaithersburg, Maryland See http://csrc.nist.gov/rng/.
• 51: Martina F. Schollmeyer , William H. Tranter, Noise generators for the simulation of digital communication systems, Proceedings of the 24th annual symposium on Simulation, p.264-275, April 1991, New Orleans, Louisiana, United States
• 52: Teichroew, D. 1953. Distribution sampling with high speed computers. (PhD thesis).
• 53: Thomas, D. B. and Luk, W. 2006. Non-uniform random number generation through piecewise linear approximations. In International Conference on Field Programmable Logic and Applications.
• 54: Alastair J. Walker, An Efficient Method for Generating Discrete Random Variables with General Distributions, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.253-256, Sept. 1977 [doi>10.1145/355744.355749]
• 55: Wallace, C. 2005. Random number generators. Tech. rep., Monash University. See http://www.datamining.monash.edu.au/software/random/.
• 56: C. S. Wallace, Fast pseudorandom generators for normal and exponential variates, ACM Transactions on Mathematical Software (TOMS), v.22 n.1, p.119-127, March 1996 [doi>10.1145/225545.225554]
• 57: Wetherill, G. B. 1965. An approximation to the inverse normal function suitable for the generation of random normal deviates on electronic computers. Appl. Statis. 14, 2, 201--205.
• 58: Wichura, M. J. 1988. Algorithm AS 241: The percentage points of the normal distribution. Appl. Statis. 37, 3, 477--484.
• 59: Xilinx. 2002. Additive white Gaussian noise (AWGN) core. CoreGen documentation file.

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
Gaussian, Random numbers, normal, simulation