4
$\begingroup$

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:

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).

$\endgroup$
  • $\begingroup$ When you say 'programmed into any application', what is the use case? Calculating $\pi$ is a fine programming exercise, but that phrase makes it sound like you feel like general applications that might have use of pi would want to calculate it... $\endgroup$ – Steven Stadnicki Aug 16 '13 at 19:28
  • $\begingroup$ I mean, I just need the pseudo code so I can understand how the mathematical formula relates to any implementation of code. $\endgroup$ – m.smakg Aug 16 '13 at 19:29
  • $\begingroup$ Unlike what your first sentence says, the title does not say much at all. What precisely are you asking? Do you want pseudo-code for computing the specific formula you gave? That is is straightforward (set $k=0$, compute the expression, add $1$ to $k$, recompute the expression and add, repeat indefinitely) but hides all important details (just what does "compute the expression" really do?). Do you want alternative methods? What is your purpose (certainly you are not going to find and new digits of$~\pi$)? Please explain the real question more clearly. $\endgroup$ – Marc van Leeuwen Aug 17 '13 at 5:02
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, I'll look into it and then select the best answer! $\endgroup$ – m.smakg Aug 16 '13 at 20:08
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm a novice in mathematics (only middle school!), is it possible for you to help me understand the equation? I see that it is probably the best method as it was used to calculate $\pi$ in many world record situations. $\endgroup$ – m.smakg Aug 16 '13 at 19:22
  • 1
    $\begingroup$ You could also use some of the algorithms given here, especially the ones from the 1980's: en.wikipedia.org/wiki/Borwein%27s_algorithm or this method: en.wikipedia.org/wiki/Gauss%E2%80%93Legendre_algorithm $\endgroup$ – user84413 Aug 16 '13 at 19:26
  • 1
    $\begingroup$ You first plug k=0 into the formula after the summation "Sigma" symbol, then k=1, and so on, until you reach the final value of k you want, and you add up all the numbers you get. Hopefully exponents and such make sense to you; the only thing you might not know is "factorial" which is denoted "N!" which means you multiply all the integers 1*2*3*...*N together. (and 0! is defined to be 1) $\endgroup$ – user2566092 Aug 16 '13 at 19:26
  • $\begingroup$ @user2566092, thanks, that helps me, but where does the $k$ increment? And where did the numbers such as 13591409 or 545140134k come from? And why is it the sum of k=0 $\sum$ to infinity, multiplied by 12 to get $1/\pi$? $\endgroup$ – m.smakg Aug 16 '13 at 19:32
  • 1
    $\begingroup$ You keep incrementing k starting at 0 and ending whenever you want / whatever your system can handle, and add up all the terms you get from k=0 to the end point to get a good estimate for 1/pi. As for where all the big numbers come from in the formula, and why the formula is completely correct when you add up the "infinitely many terms" for all k >= 0 that is very deep mathematics that I don't even understand. :) But the terms get very small very fast as k increases, which is why this is a very efficient way to estimate pi. $\endgroup$ – user2566092 Aug 16 '13 at 19:43
1
$\begingroup$

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$.

circle area

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)

$\endgroup$
  • $\begingroup$ It reaches machine precision extremely quickly because each iteration gives about 14 digits. $\endgroup$ – George V. Williams Aug 16 '13 at 23:38
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.