AGM Methods
Last Modified: August 15, 2003
Around 1800, Gauss discovered the "arithmetic-geometric mean" identity for elliptic 
integrals.  When rediscovered two centuries later, this led to some of the most efficient 
techniques for computing pi to millions of decimal places. 
Requires
Derivatives and Integrals
References:
Pi Source Book, pages 553-556(Newman) (attached for convenience)
Pi Source Book, pages 418-423(Salamin)
Pi Source Book, pages 423-433(Brent)
Pi Source Book, pages 537-552(the Borweins)
Pi Source Book, pages 623-642(the Borweins and Bailey)
Pi Source Book, pages 562-575(Bailey)
Pi Source Book, pages 588-595(Scientific American)
"How Gauss Could Have Analyzed the Simple Pendulum" (attached)
Minilectures 1 and 2:
Following the approach of Newman (which avoids most of the complications of elliptic integrals), outline the technique for calculating p using the arithmetic-geometric mean (AGM).
There are four parts to this.  Your presentation will probably be more enlightening if you present numerical examples for some of the steps instead of slogging through lots of algebra.
Minilecture 1: Gauss's discovery of the AGM

1. Start with the elliptic integrals 
and 
and show that the change of variable  
transforms the second into the first. Careful - x -> 0 corresponds to t -> -

2. By iterating this transformation, derive Gauss's formula

where m(a,b) is the AGM of a and b, obtained by iterating the recursion
(a, b) -> () until the two quantities a and b achieve a common value m.

Minilecture 2: Newman's calculation of p.

1. With Newman, define the "harmonic-geometric mean"
h(a,b) = ab/m(a,b), which can be obtained by iterating

(a, b) -> ()
Start with

and show that 

h(N,1) = 
Note that  .
This explains the mysterious identity on p.209 of Newman.

2. Finally, show that 
N(h(N+1,1) - h(N,1)) = 2/p + O(1/N)

Here is a worksheet that shows how to compute p using Newman's version of the AGM. Below, n is the number of desired bits of accuracy for p.  Each 10 bits gives 3 digits.  Since the computations have to keep twice as many digits as are required in the final value for pi, and since MathCAD only keeps about 15 digits (50 bits), 25 is a reasonable upper limit here. This approach requires infinite-precision arithmetic to give high accuracy.

Set up the starting values:

Now carry out the AGM iteration until a and b are equal

Now we have to repeat the process, using N+1 instead of N

From the two values of the AGM, we can calculate p

Minilecture 3: Gauss and the simple pendulum (for a physicist)
A famous "unsolvable" problem of elementary physics is to calculate the period of oscillation of a pendulum of arbitrary amplitude.  In fact, the problem can be solved quite efficiently by the AGM method, and the answers agree with the ones cited in books on elliptic integrals.
In the spirit of Newman, one can consider the special case of a pendulum that is released from rest when it is almost precisely upside down.  Combining this limiting case with the AGM gives a value for pi!

Don't go through all the gory details of the calculation.  Instead, use the program AGM.exe on the course Web site to illustrate how the calculation is done.
Minilecture 4 (computational):
The last four references all contain recursive AGM algorithms for computing p that are easier to implement (though harder to prove) than Newman's.  Choose two and use them to get lots of digits of p.  2000 decimal places should take less than a second.  

You will need high-precision arithmetic, but that is built into Mathematica.
You can check your answers against pages 330-349 of the Pi Source Book or against the built-in value for p in Mathematica. Better, you can implement two different algorithms and insist that they agree.

If you want to calculate more than a couple of thousand digits, don't display them all.
Just calculate and display the difference between your calculated value of p and Mathematica's value, or between two values that you have calculated by different algorithms.

The best-known AGM algorithms exhibit "quadratic convergence."  This means that the
percentage error is squared with each iteration, so that the number of correct decimal
places doubles with each iteration. Some of the algorithms in the source book, notably ones in the Scientific American article, converge even faster.  Demonstrate this rapid convergence by showing the results of different numbers of iterations.