sicp-ex-1.31


a.

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

factorial function, in terms of product function above, can be written as below.

  
 (define (identity x) x) 
  
 (define (next x) (+ x 1)) 
  
 (define (factorial n) 
 (product identity 1 next n)) 

approximations to pi using john wallis' formula, can be found by defining a new term to be used by product function as below

 (define (pi-term n) 
   (if (even? n) 
       (/ (+ n 2) (+ n 1)) 
       (/ (+ n 1) (+ n 2)))) 

And it can be used as follows.

 (* (product pi-term 1 next 6) 4)   ;;= 3.3436734693877552 
 (* (product pi-term 1 next 100) 4) ;;= 3.1570301764551676 

b.

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

Another approach would be to recognize the series as 4*4*6*6*.../3*3*5*5*... The leading factor of 2 in the numerator must be dealt with.

 (define (pi n) 
   (define (term x) (* x x)) 
   (define (next x) (+ x 2)) 
   ; since we are increasing the numbers by two on every iteration 
   (define limit (* n 2)) 
   ; upper term: - 2 always goes first, start building product from 4 
   ;             - as 2 numbers are skipped, the limit must respect that, too 
   ;             - since we are squaring one time too often at the end, 
   ;               we have to divide that back out of the result 
   ; lower term: start with 3, which is 1 more than the upper term 
   ;             -> so increase limit by 1 
   ;  
   (* 4 (/ (/ (* 2 (product term 4 next (+ limit 2))) 
              (+ limit 2)) 
           (product term 3 next (+ limit 1))))) 

Yielding:

 (pi 6) ;;= 3.255721745 
 (pi 100) ;;= 3.149378473 

n defines steps in terms of pairs of factors. So where the above solution does 6 steps when n=6, this solution does 12 steps when n=6:

 (pi 3) ;;= 3,343673469 
 (pi 50) ;;= 3,157030176 

<< Previous exercise (1.30) | sicp-solutions | Next exercise (1.32) >>