Re: Factor

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.