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.
No comments:
Post a Comment