## Sunday, September 25, 2011

### Approximating Pi

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 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:

```( 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.