STANFORD UNIVERSITY

Stanford 50: State of the Art and Future Directions of Computational Mathematics and Numerical Computing

Information

  • March 29, 2007
  • 9:50 am - 10:15 am

George Forsythe's last paper

Richard Brent (Australian National University)

In 1949 George Forsythe attended some lectures at UCLA by John von Neumann on the topic of random number generation. Shortly before he died, Forsythe wrote a Stanford report STAN-CS-72-254 inspired by von Neumann's lectures. It was intended that this would form the basis of a joint paper with J. H. Ahrens and U. Dieter, who had discovered related results independently. However, after Forsythe died in April 1972, Don Knuth submitted the Stanford report to Mathematics of Computation and it was published with only minor changes as "Von Neumann's comparison method for random sampling from the normal and other distributions" Math. Comp. 26, 1972, 817-826). This was Forsythe's last published paper, with the possible exception of a paper "Variational study of nonlinear spline curves" by E. H. Lee and Forsythe in SIAM Review (submitted before Forsythe's death but not published until 1973).

Ahrens and Dieter published a follow-up paper "Extensions of Forsythe's method for random sampling from the normal distribution" Math. Comp. 27, 1973, 927-937), and I published an implementation "Algorithm 488: a Gaussian pseudo-random number generator" (Comm. ACM 17, 1974, 704-706).

In this talk I will describe von Neumann's elegant idea for sampling from the exponential distribution, Forsythe's generalization for sampling from a probability distribution whose density has the form exp(-G(x)), where G(x) is easy to compute (e.g., a polynomial), and my refinement of these ideas to give an efficient algorithm for generating pseudo-random numbers with a normal distribution. I will also (very briefly) mention some later developments.


Stanford University Home Page