Algorithm 488: A Gaussian pseudo-random number generator

ABSTRACT

The algorithm calculates the exact cumulative distribution of the two-sided Kolmogorov-Smirnov statistic for samples with few observations. The general problem for which the formula is needed is to assess the probability that a particular sample comes from a proposed distribution. The problem arises specifically in data sampling and in discrete system simulation. Typically, some finite number of observations are available, and some underlying distribution is being considered as characterizing the source of the observations.

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: Ahrens, J.H., and Dieter, U. Pseudo-random Numbers (preliminary version). Preprint of book to be published by Springer, Part 2, Chs. 6-8.
• 3: Brent, R.P. Algorithms for Minimization Without Derivatives. Prentice-Hall, Englewood Cliffs, N.J., 1973, pp. 163-164.
• 4: Forsythe, G.E. Von Neumann's comparison method for random sampling from the normal and other distributions. Math. Comp. 26, 120 (Oct. 1972), 817-826.
• 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: Von Neumann, J. Various techniques used in connection with random digits. In Collected Works, Vol. 5, Pergamon Press, New York, 1963, pp. 768-770.
• 7: 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]
• 1: C. Bron, Merge sort algorithm [M1], Communications of the ACM, v.15 n.5, p.357-358, May 1972 [doi>10.1145/355602.361317]
• 2: Bron, C. An "In Situ" Merge Sort Algorithm. Tech. Note CB 64, Technological University of Twente, Enschede. The Netherlands.
• 3: W. A. Martin, Sorting, ACM Computing Surveys (CSUR), v.3 n.4, p.147-174, Dec. 1971 [doi>10.1145/356593.356594]
• 1: Bellmore, M., and Nemhauser, G.L. The traveling salesman problem: A survey. Oper. Res. 16 (1968), 538-558.
• 2: Berge, C. The Theory of Graphs and Its Applications. Wiley, New York, 1962.
• 3: Berge, C., and Ghouila-Houri, A. Programming, Games and Transportation Networks. Wiley, New York, 1965.
• 4: Boothroyd, J. Algorithms 22, 23, 24. Shortest path. Comp. J. 10 (1967), 306-308.
• 5: Lee, C.J. An algorithm for path connections andits applications. IEEE Trans. Elect. Comput. EC-IO (Sept. 1961), 346-365.
• 6: Akers, S.B. A modification of Lee's path connection algorithm. IEEE Trans. Elect. Comput. (Feb. 1967), 97-98.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
Gaussian distribution, normal distribution, pseudo-random numbers, random numbers