\documentclass[11pt]{article}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{epstopdf}
\usepackage{hyperref}
\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png}

\hyperbaseurl{http://www.phaser.com/modules/historic/gaussagm/}

\textwidth = 6.5 in
\textheight = 9 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
\topmargin = 0.0 in
\headheight = 0.0 in
\headsep = 0.0 in
\parskip = 0.2in
\parindent = 0.0in

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{lemma}{Lemma}

\title{AGM calculation of Pi}
\author{Burton Rosenberg}
\begin{document}
\maketitle

\section*{Highlights}

{\bf Historic:} 

In 1799, Gauss was startled to discover that his {\em arithmetic-geometric mean}
connected $\varpi$,
the half-circumference of a curve known as the lemniscate, 
with $\pi$, the half-circumference of a unit circle:
\begin{quote}
That the AGM is equal to $\pi/\varpi$ between 1 and $\sqrt{2}$ we have confirmed
up to the 11-th decimal digit; if this is proven, then a truly new field of analysis stands
before us.
\end{quote}
Gauss also found efficient ways of computing many elliptic integrals, including
those for $\varpi$, thus giving an extremely fast algorithm for the computation of $\pi$. 

In 1976 the method was 
rediscovered independently by Brent and Salamin and stands currently
as among the fasted known methods for calculating $\pi$.


{\bf Mathematical:}

The half-circumference $\varpi$ of the lemniscate curve is given by an
{\em elliptic integral of the first kind.}  
This integral can be related to $\pi$ using another elliptic integral, one
said to be of {\em the second kind.}
Elliptic integrals can be numerically evaluated with the help of an iterative
process known as the arithmetic-geometric mean.
Combining these integrals it is possible to express $\pi$ in a manner
suitable for efficient numerical evaluation.

\section*{Equations}
\begin{eqnarray*}
x_1 &\rightarrow& (x_1+x_2)/2\\
x_2 &\rightarrow& \sqrt{x_1x_2}\\
x_3 &\rightarrow&  x_3 - x_4(x_1-x_2)^2/4\\
x_4 &\rightarrow& 2\,x_4 \\
x_5 &\rightarrow& (x_1+x_2)^2/(2\,x_3)
\end{eqnarray*}

{\bf Variables}
\[
\begin{array}{lcl}
x_1 &:& \mbox{the arithmetic mean}\\
x_2 &:& \mbox{the geometric mean}\\
x_3 &:& \mbox{the arc length of a lemniscate}\\
x_4 &:& 2^k\\
x_5 &:&\mbox{the $k$-th convergent to $\pi$}
\end{array}
\]

\section*{Dynamics}
%\begin{center}
%\href{https://jupiter.math.miami.edu/modules/historic/gaussagm/gaussagm.ppf}{
%\href{gaussagm.ppf}{
%\includegraphics{gaussagm.eps}}
%\end{center}

\section*{Discussion}

Gauss's fast method for the computation for the circumference of a circle
begins with investigations into the circumference of another plane curve,
the {\em lemniscate}. In polar coordinate, the leminscate is given by,
\[
r^2 = \cos 2 \theta.
\]
This curve was intriguing to Gauss and others because
it had mathematical properties related to the circle.
The half circumference of the leminscate is $\varpi = 2\,I(\sqrt{2},1)$,
where $I(a,b)$ is the {\em elliptic integral of the first kind},
\[
  I(a,b) = \int_0^{\pi/2} \frac{d\theta}{\sqrt{a^2\cos^2\theta + b^2\sin^2\theta}}.
\]
In fact, the symbol $\varpi$ for  the half-circumference
of a ``unit radius'' leminscate is a variant of $\pi$, the symbol for the
half-circumference of a ``unit radius'' circle.

Although elliptic integrals are exceeding common and
important in practice, they are impossible to evaluate 
analytically.
Gauss showed that these integrals can be numerically
evaluated by successively replacing
$a$ and $b$ by their arithmetic and geometric means,
\begin{eqnarray*}
   a_{i+1} &=& (a_i+b_i)/2\\
   b_{i+1} &=& \sqrt{a_ib_i}
\end{eqnarray*}
where $a_0=a$ and $b_0=b$.
The sequence $a_i$ and
$b_i$ converge extremely quickly to a common value, called the {\em arithmetic-geometric
mean of $a$ and $b$}, denoted ${\rm AGM}(a,b)$.  
Specifically,  in 1799 Gauss discovered that if $a_i$ and $b_i$ follow 
from $a$ and $b$ as a result of one
or several steps of the AGM procedure, the integral is unchanged, $I(a,b)=I(a_i,b_i)$.
Hence, in the limit, the common value ${\rm AGM}(a,b)$ can be factored out and the integrand
collapses to $1/\sqrt{\cos^2\theta+\sin^2\theta}=1$,
\[
I(a,b)=\frac{\pi}{2\,{\rm AGM}(a,b)},
\]
and in particular, 
\[
\pi / \varpi = {\rm AGM}(\sqrt{2},1).
\]

Gauss found this result astounding.
A qualitative relationship between the theory of leminscates and circles had
been noted, and now it was found that the ratio of the fundamental constants
in the two theories are related by a value proceeding from the process of
arithmetic-geometric mean!

An additional relation is required in order to use the AGM to calculate 
$\pi$, rather than the ratio $\pi/\varpi$. Among the various elliptic integrals
under study at that time, there were those of the second kind,
\[
L(a,b) = \int_0^{\pi/2} \frac{\cos^2 \phi\,d\phi}{\sqrt{a^2 \cos^2\phi+b^2\sin^2\phi}}.
\]
Gauss also gave a method to numerically evalute $L(a,b)$ using the AGM,
\[
c_0^2L(a,b)  = (c_0^2-S)I(a,b),
\]
where,
\[
S=\sum_{k=0}^\infty 2^{k-1}c_k^2,
\]
$c_i^2=a_i^2-b_i^2$, and the $a_i$ and $b_i$ are the iterates
in the AGM process of $a$ and $b$. 

In 1748, Euler discovered that, 
\[
L(\sqrt{2},1) I(\sqrt{2},1) = \pi/4
\]
Substituting this into the relations above, Gauss derived, 
\[
\pi = \frac{{\rm AGM}(\sqrt{2},1)^2}{1-S}.
\]
The use of this formula is that the AGM converges extremely quickly, and the values $c_i$,
required in the evaluation of the sum $S$,
converge towards zero extremely quickly. With just several terms we already have a very
good approximation of $\pi$.

A map suitable for Phaser is derived from this formula. Let $x_1$ and $_2$ be $a_i$
and $b_i$, $x_3$ be $1-S$,  the sum $S$ truncated to the first $k$ terms, and $x_4$
be $2^k$. At each iteration,
\begin{enumerate}
\item
$x_1$ is updated to be the arithmetic mean of $x_1$ and $x_2$;
\item
$x_2$ is updated to be the geometric mean of $x_1$ and $x_2$;
\item
$x_3$ is updated to include an additional term; 
\item $x_4$ is updated to $2 x_4 = 2^{k+1}$.
\end{enumerate}
The update of $x_3$ requires  values for $c_k^2$ and $2^k$. 
Note that $c_i^2$ can be written as $(a_{i-1}-b_{i-1})^2/4$, 
which reduces the amount of computation needed to derive this value.
The value of $2^k$ is available in $x_4$.

Let $x_5$ be the approximation to $\pi$ given by the current approximation
to $\rm{AGM}(1,\sqrt{2})$ and $S$. At each iteration we compute this from
$x_1$, $x_2$ and $x_3$. It is customary to take as the approximate value of
the AGM at step $i$ to be the arithmetic mean of $a_i$ and $b_i$.


\section*{References}

Jorg Arndt, Christoph Haenel, {\em $\pi$ Unleashed}, Spring-Verlag, 2000.

Lennart Berggren, Jonathan Borwein, Peter Borwein, {\em Pi: A Source Book}, Spring-Verlag, New
York 1997.

Richard P. Brent, {\em Fast multiple-precisions evaluation of elementary functions},
J. of the ACM, Vol. 23, No. 2, April 1976. pp. 242--251. See also Berggren [1997].

David A. Cox, {\em The arithmetic-geometric mean of Gauss},  L'Enseignement Math\'{e}matique,
t. 30, 1984. pp. 275--330. See also Berggren [1997].

Carl Friedrich Gauss, {\em Werke}, Gottingen, 1866--1933.

%C. C. J. Jacobi, {\em Gesammelte Vwerke}, G. Reimer, Berlin, 1881.

Nick Lord, {\em Recent calculations of $\pi$, the Gauss-Salamin algorithm},
The Mathematical Gazette, Vol. 76, No. 476, July 1992. pp 231--242.

Eugene Salamin, {\em Computation of $\pi$ using arithmetic-geometric mean},
Mathematics of Computation, Vol. 30, no. 135, July 1976. pp 565--570. See also Berggren [1997].


 \end{document} 