SICP-2nd-Edition-Exercise-1.31

From Boozled

Exercise 1.31 From SICP

a. The (sum) procedure is only the simplest of a vast number of similar abstractions that can be captured as higher-order procedures.55 Write an analogous procedure called (product) that returns the product of the values of a function at points over a given range. Show how to define (factorial) in terms of (product). Also use (product) to compute approximations to $π$ using the formula 52

$\frac{\pi}{4} = \frac{2\cdot4\cdot4\cdot6\cdot6\cdot8\ldots}{3\cdot3\cdot5\cdot5\cdot7\cdot7\ldots}$

b. If your (product) procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.

Attempt

Part a

The mathematical notation for sum and product is as follows

$Sum = \sum_{k=1}^N k^2$

$Product = \prod_{k=1}^N k^2$

In both these expressions there are four things happening.

* Test
* Calculate
* Operate
* Step

Our Operate is either Sum or Product in the above examples. The fact that both expressions have four things happening means we could probably abstract further than the question has asked us to but I think some of the next exercises asks us to do that so I won't bother in this one.

We are asked to implement (factorial) in terms of (product) using this method. Have a look at SICP-2nd-Edition-Exercise-1.30. You can see all the expressions listed above. To implement (factorial) you need only change (+ result (calc a)) to (* result (calc a)) and change the name and you have it. All we done here was change from the Sum to the product operator.

Implementing the Wallis Product (at Wikipedia) algorithm appears quite straight forward but it requires careful handling. For instance if we want to calculate the Product up to 8 do we mean where 8 first appear in the denominator or last appears in the numerator etc. I am making the assumption that the product we are calculating always starts the same way as above otherwise we could try and use (define (walliscalcs n) (/ (square n) (square (+ n 1)))) and this method comes with its own set of headaches.

One way to look at the equation above is as follows.

$\frac{\pi}{4} = \frac{2\cdot4\cdot6\cdot8\ldots * 4\cdot6\cdot8\ldots}{3\cdot5\cdot7\cdot9\ldots * 3\cdot5\cdot7\cdot9\ldots}$

If we go down this route we end up with something like.

(define (step2 x)(+ x 2))
(define (calc a) a)
(define stop 170)
(display (*
          (/ (* (my-product calc 2.0 step2 (- stop 2)) 
                (my-product calc 4.0 step2 stop) )
             (* (my-product calc 3.0 step2 stop)
                (my-product calc 3.0 step2 stop) )
             )
         4))

This is a very bad method to calculate the product because it is dependent on an even input and the products get so large they become unwieldy on the computer (I eventually got NaN as things got really large). We could still use this method if we broke the numbers up a bit and done some intermediate calculations but that would be a PITA.

Another way to look at this is is as follows:

$\frac{\pi}{4} = \lim_{n \to \infty}\left[\frac{2}{3} \cdot \frac{4}{5} \cdot \frac{6}{7} \ldots \frac{n}{n+1} \quad * \quad \frac{4}{3} \cdot \frac{6}{5} \cdot \frac{8}{7} \ldots \frac{n+1}{n}\right]$

This is a better way than previous and gives us.

(define (step2 x)(+ x 2))
(define (walliscalcp n) (/ n (+ n 1)))
(define (walliscalcn n) (/ n (- n 1)))
(define stop 3000940)
(display (*
          (* (my-product walliscalcp 2.0 step2 stop) 
             (my-product walliscalcn 4.0 step2 stop))          
         4))

Note the two different calculations walliscalcp and walliscalcn. The equation assumes we are calculating out to infinity and when you run it you will see that it approaches $π$ very slowly. Again we can do this using one walliscalc procedure if we calculate $\frac{\pi}{2}$ . Please note I have not tried to make sure that the number of integers in the numerator match the denominator.

Part b

Please look in the book at the recursive sum algorithm.

Scheme

; There is a lot of messy code in here and some leftovers that will 
; give you an idea of the working I tried etc.
(define (calc a) a)
(define (step a) (+ a 1))
(define (my-sum calc a next b)
  (define (iter a result)
    (if (> a b) 
        result
        (iter (next a) (+ result (calc a))  )))
  (iter a 0))
 
(define (my-product calc a next b)
  (define (iter a result)    
    (if (> a b) 
        result
        (iter (next a) (* result (calc a)))
        ))
  (iter a 1))
 
(define (square x) (* x x))
(define (walliscalcp n) (/ n (+ n 1)))
(define (walliscalcn n) (/ n (- n 1)))
(define (walliscalcs n) (/ (square n) (square (+ n 1))))
(define (step2 x)(+ x 2))
 
(define stop 100000)
(define (wallis b)
     (* 4
        (* (my-product walliscalcp 2.0 step2 b) 
           (my-product walliscalcn 4.0 step2 b))          
        ))
 
(display (wallis 20000))
 
(newline)
(display (my-product walliscalcs 2 step2 4) )
 
(newline)
(display (my-product walliscalcs 3 step2 5) )
 
;(define (wallisloop s n) 
;  (display (wallis s)) (newline)
;  (if (> s n) 
;      0
;      (wallisloop (+ s 1) n))  
;      )
;
;(display (wallisloop 1 1300))