## Approximating Pi

Sunday, September 25, 2011

A few days ago, it was
announced on
the Wolfram Blog that a 13-year-old had made a record calculating 458
million terms for the continued fraction of `pi`

. In the spirit of that,
I thought I would show how to solve a question that sometimes gets asked
at interviews:

Given that Pi can be estimated using the function 4 * (1 - 1/3 + 1/5 - 1/7 + …) with more terms giving greater accuracy, write a function that calculates Pi to an accuracy of 5 decimal places.

Using Factor, we can calculate the `nth`

approximation of `pi`

using vector
arithmetic:

```
: approximate-pi ( n -- approx )
[1..b] 2 v*n 1 v-n 1 swap n/v
[ odd? [ neg ] when ] map-index sum 4 * ;
```

This isn’t ideal if we want to try an increasing number of terms (looking for a particularly accuracy), since a lot of the work would be redone unnecessarily. Instead, we can write a word that adds successive terms until the difference between the previous approximation and the current approximation is less than our requested accuracy.

```
: next-term ( approx i -- approx' )
[ 2 * 1 + ] [ odd? [ neg ] when ] bi 4.0 swap / + ; inline
:: find-pi-to ( accuracy -- n approx )
1 4.0 [
dup pick next-term [ - ] keep
swap abs accuracy >= [ 1 + ] 2dip
] loop ;
```

To show its performance, we can time it:

```
IN: scratchpad [ 0.00001 find-pi-to ] time .
Running time: 0.026030341 seconds
3.141597653564762
```

An equivalent function in Python might look like this:

```
def find_pi_to(accuracy):
i = 1
approx = 4.0
while 1:
term = (2 * i) + 1
if i % 2 == 1:
term = -term
new = approx + 4.0/term
if abs(new - approx) < accuracy:
approx = new
break
i += 1
approx = new
return approx
```

But, if we time this version (not counting startup or compile time), it takes 0.134 seconds. Doing the math shows that Factor is 5 times faster than Python in this case. Not bad.