You are here

The SIAM 100-Digit Challenge: A Study in High-Accuracy Numerical Computing

Folkmar Bornemann, Dirk Laurie, Stan Wagon, and Jorg Waldvogel, editors
Publisher: 
SIAM
Publication Date: 
2004
Number of Pages: 
306
Format: 
Paperback
Price: 
57.00
ISBN: 
0-89871-561-X
Category: 
Anthology
[Reviewed by
Douglas Faires
, on
11/4/2008
]

I started this review numerous times, and in each instance have become so engrossed with the material that the review got lost in the process. This, I can assure you, is high praise, since my attention span is not generally that long.

The book is based on a challenge posed by Nick Trefethen of Oxford University in the 2002 January/February issue of SIAM News. The challenge, in short, was to determine the solution to 10 problems, and each solution was to be accurate to the 10 leading digits. The challenge was made to all members or teams of members of the SIAM community. The problems were based on some given to his graduate students in numerical analysis at Oxford University, and the contestants in this particular contest could be either individuals or teams of individuals.

A prize of $100 was offered to any individual or team that provide the most accurate results, that is, the largest number of correct digits, by 20 May 2002. The problems were said to be difficult and Trefethen stated in the challenge that "If anyone gets 50 digits in total, I will be impressed."

Well, impressed he must have been; first by the number of contestants (94), and also by the number that obtained all 100 correct digits (20), with 5 additional teams obtaining all but 1 correct digit. Among the "teams" that obtained all the correct digits, 4 were individuals, as were 4 of 5 who obtained 99 digits correct. Some of the teams came from the same institutions, but others involved people from multiple countries and even from multiple continents. This was truly an international contest.

As stated in their Preface, the authors of this book are from four different countries and three different continents, and they did not know each other prior to the contest. Since each chapter had one member as its lead author, the writing style varies a little. However, the book is generally easy to read for anyone with a minimal background and interest in scientific computing.

What makes the book so attractive is the extensive description the methods used by the competitors for solving the individual problems. It is not the actual solution to the individual problems that I find so interesting. Rather it is the number and variety of different approaches to the solution that the authors present that makes it a book that I think could easily be titled Techniques that Everyone Doing Numerical Computation Should Know.

Let me take just two examples to illustrate. These are admitted two of my favorites, but I could have chosen almost any pair for this purpose.

Problem 1: What is /sites/default/files/images/cms_upload/foo02089.jpg?

This improper integral is highly oscillatory near x = 0 and nearly zero after about 0.2. The following are described as methods of solution for this problem:

  • Apply Romberg integration on the subintervals between the roots of the integrands;
  • Use complex integration and Euler's formula to convert it to an exponential integrand whose real part will provide the solution;
  • Recognize that Lambert's W function can be applied to determine the solution;
  • Transform the integral by using t = –log x, then convert to a complex exponential form and use integration by parts;
  • After converting to the complex form use contour integration;
  • Recognize that after the transformation t = –log x an integral results that has the form of a Fourier integral that can be solved by standard computer algebra packages using the Ooura-Mori technique.

Problem 10: A particle at the center of a 10x1 rectangle undergoes Brownian motion (i.e., a two-dimensional random walk with infinitesimal step lengths) until it hits the boundary. What is the probability that it hits one of the ends rather than one of the sides?

This problem was the solved by the fewest number of teams, but most of the teams submitting a solution had all 10 digits correct. First the authors show why a standard Monte Carlo technique is not suitable: it would require many more arithmetic calculations than it has been estimated have ever been performed by man or machine. (This type of side remark is common in the book, and adds considerably to its readability.)

Methods of solution employed for this problem include the following:

  • Extend to a problem with varying initial point, then consider the problem as the discretization of Laplace's equation with Dirichelet boundary conditions and look at this problem analytically;
  • Solve the discrete problem using Cholesky's method and a fast Poisson solver available, for example, in MATLAB;
  • Apply extrapolation to the results of the previous technique to accelerate the convergence;
  • Solve the boundary value problem using a classic separation of variable technique;
  • Use a classic infinite series identity of Cauchy involving the hyperbolic secant function;
  • Use conformal mapping to solve the problem analytically, employing the Schwarz-Christoffel transformation, and then solve the resulting elliptic integral numerically;
  • Use singular moduli results and identities of Abel, Kronecker, Ramanujan, and others which produce a closed form, exact, solution to the problem.

I hope this gives some indication of the wide range of ideas that are discussed in the book, and which give solutions to some difficult — often diabolical — problems. The authors also consider extensions of the problems to more difficult situations, describing why some of the techniques used to solve the original problem will still prevail, but others will not give successful results.

Finally, there is a wonderful appendix on accelerating convergence. This runs nearly 35 pages and is recommended reading for anyone interested in numerical approximation. It includes my favorite extrapolation application, which involves Archimedes approximation to π. A second appendix discusses extreme-digit hunting, and discusses the authors' attempts to find not 10, but 10,000 correct digits for each of the contest problems. Finally, there is a short appendix listing code that was used. The web site for the book links to the site of Folkmar Bornemann, where the code is located.

In summary, this book should be on the desk of anyone doing numerical computation on even an irregular basis. But more importantly, it is a valuable addition to the library of anyone who appreciates seeing the variety of ways that clever people think of when approaching a difficult problem.


Doug Faires is Professor Emeritus at the Department of Mathematics of Youngstown State University.

Foreword; Preface; The Story; Chapter 1: A Twisted Tail; Chapter 2: Reliability amid Chaos; Chapter 3: How Far Away Is Infinity?; Chapter 4: Think Globally; Act Locally; Chapter 5: A Complex Optimization; Chapter 6: Biasing for a Fair Return; Chapter 7: Too Large to Be Easy; Too Small to Be Hard; Chapter 8: In the Moment of Heat; Chapter 9: Gradus ad Parnassum; Chapter 10: Hitting the Ends; Appendix A: Convergence Acceleration; Appendix B: Extreme Digit-Hunting; Appendix C: Code; Appendix D: More Problems; References; Index.