sicp-1.31-solution

So I’m trying to make way through Structure and Interpretation of Computer Programs, and it’s going pretty slow but it is definitely amusing and smashing !!! absolutely smashing. Don’t be shy to grab a copy if you can afford to (I mean a physical copy)

So I came with a solution to the following problem that I am a bit proud of and hence I am writing on here about it.

So here’s the question (It’ a part of question 1.31 of sicp, won’t be covering the whole question)

... Also use product to compute approximations to pi using the formula

(pi/4) = (2.4.4.6.6.8 ...)/(3.3.5.5.7.7 ...)

So here’s a little info n what this product function is. All it is is a specific form of fold/reduce

(define (product a b next term)
  (if (> a b)
     1
     (* (term a) (product (next a) b next term))))

Given a range and a function to generate the next item in the sequence (next) alongside yet another function (term) that is a function that operates on each term, you get the product of the resultant terms after mapping the term function over the range.

The resemblance to fold reduce may seem a little hazy because you cannot see the accumulator clearly so let’s go on a more tail-recursive or iterative-process form of the function

(define (product a b next term)
 (define (iter a accumulator)
   (if (> a b)
     accumulator
     (iter (next a) (* (term a) accumulator))))
  (iter a 1))

And there you go !!!! you ought to see it by now right?

So now moving on the more exciting part i.e calculation of pi via the above function

After a while of coming up with not so elegant solutions I came up with this solution

Do keep in mind that to know the nth term of an arithmetic sequence you use the
formula:

a_n = a_0 + (n-1)*d

where d is the difference between each consecutive term

So bound with this knowledge, let’s proceed

Now look at the pi formula again

(pi/4) = (2.4.4.6.6.8 ...)/(3.3.5.5.7.7 ...)

The same can be re-written as

(pi/4) = (2*(1/3)*4*(1/5)*6*(1/7) ...) * ((1/3)*4*(1/5)*6*(1/7)*8)

if you look at the right hand side of the equations the two separations have the same number of terms!!! so no weird asymmetrical patch-ups that would normally induce ugliness !!!

So now all we need to so is use the product function to generate a stream that produces even numbers as it is, and odd number as their multiplicative inverse

AND WE NEED TO DO IT TWICE !!!! one for each separation (by separation, I mean the huge stuff with the parenthesis on each side of the multiplicative sign on the right hand side of the equation)

So now we have

(define (pi n)
 (define (inv a)
   (if (even? a)
     a
     (/ 1 a)))
 (* 4 (* (product 2 (+ 2 (- n 1)) inc inv)
         (product 3 (+ 3 (- n 1)) inc inv))))

And if you are wondering where did the 4 come from? it’s from the left side of the pi equation.

And there you go, nice and sweet.

Quotes by an okay chap