C. S. Wallace
Abstract
Fast algorithms for generating pseudorandom numbers from the unit-normal and unit-exponential distributions are described. The methods are unusual in that they do not rely on a source of uniform random numbers, but generate the target distributions directly by using their maximal-entropy properties. The algorithms are fast. The normal generator is faster than the commonly used Unix library uniform generator “random” when the latter is used to yield real values. Their statistical properties seem satisfactory, but only a limited suite of tests has been conducted. They are written in C and as written assume 32-bit integer arithmetic. The code is publicly available as C source and can easily be adopted for longer word lengths and/or vector processing.
- AHRENS, J. H. AND DIETER, U. 1989. An alias method for sampling from the Normal distribution. Computing 42, 159-170. Google Scholar
- BRENT, R.P. 1993. Fast normal random number generators for vector processors. Tech. Rep. TR-CS-93-04, Australian National Univ., Canberra, Australia.Google Scholar
- LEVA, J.L. 1992. A fast normal random number generator. ACM Trans. Math. Softw. 18, 4, 449-453. Google Scholar
Index Terms
- Fast pseudorandom generators for normal and exponential variates
Recommendations
A fast normal random number generator
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 ...
Algorithm 780: exponential pseudorandom distribution
An algorithm is presented for the calculation of exponentially distributed random numbers. It is based on mathematics that was published by Ahrend and Dieter, but some errors have been corrected.
Reviews
Kent Campbell
Wallace describes new algorithms for generating pseudorandom normal and exponential variates. Unlike standard approaches, these new algorithms do not use a stream of uniformly distributed random numbers; instead, they make repeated use of a pool of pseudorandom normally distributed variates. Unfortunately, Wallace does not offer a theoretical analysis of the new algorithms, and acknowledges that there is no obvious theory available for analysis of these algorithms (p. 126). The algorithm for the normal distribution has undergone limited empirical testing, including autocorrelation and the &khgr; 2 test for normality, with good results. The algorithm for the exponential distribution has also passed the &khgr; 2 test. Both algorithms are reported to be at least as fast as standard algorithms. C code for both algorithms is available via anonymous ftp. Anybody interested in generating pseudorandom numbers with the normal or exponential distributions would find this paper to be of interest. There is one word of caution, however. The empirical testing of these algorithms has been extremely limited. People planning on using these algorithms should test them thoroughly before using them.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments