Pseudo code for calculating $\pi$ using an iterating algorithm?

Question

So my question title says it all. What is the best way to calculate $\pi$ as an iterating algorithm that can be programmed into any application (thus the pseudo code)?

$\pi$ Was first calculated using polygons and how an internal perimeter (using a polygon) of a circle compared to the external perimeter (using a polygon) am I correct in saying this? So there must be a way to write the calculation as an iterating algorithm (in pseudo code).

In one of the answers, I found the following formula:

However, I do not understand what it means as I am a novice in mathematics (only middle school!). What I can make out is $\pi$ = $12 * \sum ((-1)^k*(6k)!(13591409 + 545140134k) )/((3k)!*(k!)^3*640420^{3k+3/2})$ The sum function is repeated to however many iterations needed. I don't understand the variable $k$ or where the formula got the numbers e.g. (6k etc).

Answer 1

I feel like your main problem is the summation, does this help?

sum = 0
for k = 0 to 100000 // Increase 100000 to whatever number for more digits
    sum += (-1)^k * (6k)! * ... // You get the idea, it's just summand
pi = 1/(12 * sum)

Why does this work? You won't like the answer; it's highly theoretical and requires far more than middle-school mathematics (I hardly understand it). If you're insistent, check out $\pi$ Formulas and read from formula 80. ("The general form of the series is ...")

May I recommend a simpler formula for computing $\pi$? Perhaps you could check out the Leibniz Series (it takes a while to get enough digits of $\pi$).

Of course, you can calculate $\pi$ by using a computer to inscribe polygons into a perfect circle. This is (1) annoying and (2) really slow compared to algorithms described here.

Another way you could compute $\pi$ which would be really nice for your level would be to use the fact that $x^2 + y^2 = 1$, and so $\sqrt{1-x^2} = y$ gives half a semi-circle, with area of $\pi/2$. By using tiny rectangles to approximate the area, you can calculate $\pi/2$. This is called a Riemann integral.

Answer 2

See http://en.wikipedia.org/wiki/Chudnovsky_algorithm for the Chudnovsky algorithm for very quickly computing pi accurately, and not too complicated to implement. The algorithm/pseudocode is that you only use the first however many terms in the series (whatever your system can handle in a reasonable computation time), and this will give you a very good approximation.

Answer 3

When I was a student I implemented the following method, of which I have absolutely no idea how it compares to other methods in terms of efficiency (probably quite bad) but which has the advantage of requiring virtually no theory whatsoever.

Of course one must be able to do arithmetic with increasingly large precision to be able to compute better and better approximations of any irrational number; this is straightforward to implement using algorithms one learns in primary school (and the method used here doesn't need long division by real numbers, just by small integers, so you need not implement the somewhat difficult general division algorithm).

One straightforward definition of $\pi$ is that $\pi/2$ is the smallest positive zero of the cosine function. Moreover the cosine function can be computed using the Taylor expansion at$~0$: $$ \cos x = 1-\frac{x^2}2+\frac{x^4}{24}-\cdots +\frac{(-x^2)^n}{(2n)!}+\cdots $$ Adding more and more terms to this series, it rapidly converges near $x=\pi/2$. So one can do an iteration in which each time one (1) increases the precision of the computation, (2) adds extra terms to the series for the cosine, and (3) performs a step of the Newton method for finding zeros of functions (since the derivative of the cosine near $x=\pi/2$ is very nearly equal to$~-1$, this just means adding to the previous value of$~x$ the newly computed value of the series for $\cos x$).

Apart from some cleverness in computing the truncated series (this one is very suited to using a Horner scheme), the only point that needs some consideration is to adjust the increases of precision/terms in (1) and (2) to what is useful given the current precision of approximation. But the method is robust in that it will increase the accuracy anyway, even if one has little idea of how precise the current approximation is. However, one can then only validate computed digits by the fact that they remain unchanged in the next iteration, while one would of course like to know how much digits of the final result are reliable.

Answer 4

Noting that

$$\sum_{k=0}^\infty f(k)=f(0)+f(1)+\cdots$$

We find that

$$\frac 1 \pi = \\12\left( \frac{(-1)^0 (6\cdot 0)!(13591409+545140134\cdot 0)}{(3\cdot 0)!(0!)^3640320^{3\cdot 0+3/2} } + \frac{(-1)^1 (6\cdot 1)!(13591409+545140134\cdot 1)}{(3\cdot 1)!(1!)^3640320^{3\cdot 1+3/2} } + \cdots\right)$$

To isolate $\pi$, take the reciprocal of both sides.

Answer 5

I am going for easiest to explain. These are absolutely, 100% NOT the best algorithms to calculate $\pi$. This should be fine, because in practice, the best algorithm is to retrieve the digits from a file or webpage! Since you are asking for pseudocode I'll give you actual javascript code, with actual programs that you can run and edit on Khan Academy's website.

The first one is the easiest to understand. I like the second one better because it doesn't use square roots, but it requires intuition about "rate of change". If you don't know how the linked programs work, you can ask questions on the Khan Academy website, or go through tutorials there.

Area of a Circle

You may know that we can describe the unit circle by the equation $x^2+y^2=1$. We can describe the upper half of the unit circle by the function $f(x)=\sqrt{1-x^2}$. We can approximate the area of the circle by dividing it into $n$ rectangles. For $n=1$ we can let our approximation be $A_1=f(0)/n=1$, since we can approximate the height of the rectangle as $f(0)$, and the width as $1/n$, and area equals width times height.

For $n=2$, we sum two rectangles: $A_2=f(0)/n+f(\frac{1}{2})/n=1/2+\frac{\sqrt{1-1/4}}{2}$.

For $n=3$, we sum three rectangles: $A_3=f(0)/n+f(\frac{1}{3})/n+f(\frac{2}{3})/n=1/3+\frac{\sqrt{1-1/9}}{3}+\frac{\sqrt{1-4/9}}{3}$.

We can write this generally: the notation for this is capital-sigma notation. $A_n=\frac{1}{n}\sum_{i=0}^{n-1}\sqrt{1-(\frac{i}{n})^2}$

As $n$ gets larger and larger we get a better and better approximation to the area, which should be, according to the area of the circle, $1/4 \pi$. So, we write $\pi=4 \lim_{n\to \infty} A_n$.

Javascript code:

var n=10;
var f=function(x){return sqrt(1-x*x);}
var areaApproximation=0;
for(var i=0;i<n;i++){
    areaApproximation+=f(i/n)/n;
}
//now areaApproximation is approximately pi/4.

(Program on Khan Academy)

Period of a Spring

This uses the remarkable properties of simple harmonic motion. Imagine you have a cart, with some amount of heft to it, attached to a giant spring which is in turn attached to a wall. The spring keeps the cart in place - if you push the cart towards the wall it will resist and try to push you away, and if you pull the cart away from the wall it will resist by pulling you towards the wall. It also has another property: If you pull the cart two meters away, you experience twice the force than if you pull it one meter away. If we pull the cart away and release it, how does it move? Solving this exact problem requires physics knowledge, but we can restate it: Suppose $f(t)$ is a function that gives the position of the object at time t. Lets say we start at $f(0)=0$, and that we push the cart so that it has a velocity of 1. What we know is that the acceleration is always proportional to how far the cart was displaced, in other words, the cart has an acceleration, at time $t$, of $-f(t)$.

Problems like these are what calculus was invented for. We say: $f(0)=0$ (the position at time $0$ is $0$), $f'(0)=0$ (the velocity at time $0$ is $1$), and $f''(t)=-f(t)$ (the acceleration at time $t$ is $-f(t)$).

It "just so happens" that the unique solution to this problem is $f(t)=\sin(t)$, with $f(0)=0$ and most importantly, $f(\pi)=0$. So, once the spring has gone from 0 all the way back to 0, $\pi$ seconds have elapsed! There's another way to solve for the function - numerically, by increasing $f$ by $f'$ and increasing $f'$ by $f''$ a bunch of times! An explanation of this would be difficult and a bit out of place here, but it is very intuitive. See if you can figure out how this code works, it uses velocity and acceleration in small time steps, and once the position springs back past 0 into the negatives, we stop the simulation and say that the total amount of time that has elapsed it an approximation to $\pi$.

var time=0;
var position=0;
var velocity=1;
var step=0.001;
while(position>=0){
    position+=velocity*step; //position increases by velocity
    velocity-=position*step; //apply "acceleration=-x"
    time+=step; //keep track of the elapsed time
}
//now "time" stores an approximation to pi

As "step" gets closer and closer to zero, the result gets closer and closer to $\pi$.

(the above code running on Khan Academy)

(Dynamic motion of a spring, on Khan Academy)

Your Formula

I'll write some code for the sake of completeness, but if you're looking for understanding or simple algorithms you should go with the above method!

(uh, the code is ugly, see George V. Williams post, I won't copy it here. Also, it gets within machine accuracy after the first two or three iterations, so make of that what you will!)

(Khan Academy implementation)