An Iterative Method of Calculating PiDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/