An Iterative Method of Calculating Pi

Date: 06/09/2004 at 17:34:50
From: Brian
Subject: A suggestion about calculating Pi

I noticed that you had listed several ways to calculate pi on your 
site, and I thought you might want to know this simple iterative method:

  P(n + 1) = P(n) + sin(P(n))

...where P(n) is the approximation of pi at iteration 'n'.  Given a 
first estimate of pi as '3.0', this converges to an approximation of 
pi correct to at least 9 digits (my calculator doesn't show more) 
after 2 iterations:

P(1) = 3 + sin(3) = 3.1411200...
P(2) = 3.14112 + sin(3.14112) = 3.141592654...

This is much faster than any other way I've seen.  I have absolutely
no idea how this works or how to prove it, I just found it on the net
somewhere and was hoping you'd publish it here where it's easier for
people to find. 

Date: 06/10/2004 at 02:52:05
From: Doctor Jacques
Subject: Re: A suggestion about calculating Pi

Hi Brian,

This is quite impressive indeed.  After the second iteration, the 
error is about 1.8*10^(-11), and, on the next iteration, the error 
drops to about 10^(-32).  This raises two questions:

  1. Why does it work?
  2. Why is it not listed as a classical way of calculating pi?

This formula is a particular case of a method used to solve an 
equation of the form:

  x = f(x)     [1]

In this case, we have f(x) = x + sin(x), and, as sin(n*pi) = 0 for any 
integer n, any multiple of pi is a solution of that equation.

An equation like [1] can sometimes be solved by iterating the formula:

  x[n+1] = f(x[n])

where x[n] is the nth approximation of the solution.  This method will 
converge to the solution if the absolute value of the derivative 
f'(x) is less than some number L < 1 in some interval containing the 
solution, and if you start with a value in that interval.  The smaller 
the derivative is, the faster the sequence will converge.

In this case, we have:

  f'(x) = 1 + cos(x)

and, if x is close to pi, cos(x) is close to -1, and f'(x) is close to 
0, which explains why the method converges rapidly.  We can also 
notice that f"(x), the second derivative, is -sin(x), which is 0 at 
the root.  This means that you can start in a relatively large 
interval about pi, and still get a very fast convergence.

We can also interpret that method as a slight modification of the 
Newton-Raphson method applied to the solution of the equation
sin(x) = 0.  The Newton method gives the formula:

  x[n+1] = x[n] - sin(x[n])/cos(x[n])

and, as cos(x[n]) is close to -1, you get your formula by replacing 
cos(x[n]) by -1 in the above formula (in fact, this converges even 
faster than Newton--with Newton, the second iteration only gives 9 
decimal places instead of 10).

This looks like a very fast and efficient method of calculating pi. 
However, the simplicity is rather deceptive.  In fact, the complexity 
is merely hidden in the computation of sin(x).  The formulas commonly 
used for calculating pi only make use of additions, multiplications, 
and divisions.  If you want to use your formula, you must be able to 
compute sin(x) for any x, and, to do that, you will need to use 
another formula (hidden behind the SIN key on your calculator), which 
will have a complexity similar to other formulas for pi.

Does this help?  Write back if you'd like to talk about this some 
more, or if you have any other questions.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/