SICP Exercise 1.31: Product of a Series

From SICP section 1.3.1 Procedures as Arguments

Exercise 1.31 asks us to write a product procedure (analogous to sum) that computes the product of a function at points over a given range. We need to show how to define factorial in terms of the new product procedure, and use product to compute approximations to π using the following formula:


Finally, if our product procedure is recursive, we need to write an iterative version, and vice versa.

Since summing a series and multiplying a series are extremely similar ideas, it's not surprising to find that it's very simple to modify sum to produce product. Let's use the recursive version from exercise 1.29 first.

(define (sum term a next b)
   (if (> a b)
       0
       (+ (term a)
          (sum term (next a) next b))))

The product procedure really only needs to perform a different operation and end on a different value than sum. The last step (when a > b) should be to multiply by 1 instead of adding 0.

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

We can test this out by implementing factorial in terms of product using the identity and inc procedures that we've used before.

(define (identity x) x)

(define (inc x) (+ x 1))

(define (factorial x)
   (product identity 1 inc x))

> (factorial 3)
6
> (factorial 4)
24
> (factorial 5)
120
> (factorial 10)
3628800
> (factorial 20)
2432902008176640000

The next test is to approximate π using something called Wallis' product or the Wallis Formula. (Lucky for us that mathematicians have already expressed this as the product of a series, saving us the work of coming up with a function for generating the terms.)


We'll multiply the product on the right hand side by the denominator on the left hand side so our procedure will just approximate π directly.

(define (wallis-pi n)
   (define (term x)
      (/ (* 4.0 (square x))
         (- (* 4.0 (square x)) 1)))
   (* 2.0 (product term 1 inc n)))

> (wallis-pi 10)
3.0677038066434994
> (wallis-pi 100)
3.133787490628163
> (wallis-pi 1000)
3.1408077460304042
> (wallis-pi 10000)
3.1415141186819313

Since our product procedure is implemented recursively, we need to show an iterative version. We can go back to the iterative sum procedure for inspiration.

(define (sum term a next b)
   (define (iter a result)
   (if (> a b)
      result
      (iter (next a) (+ (term a) result))))
   (iter a 0))

Again, there are very few changes required to transform this procedure.

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

You can plug product-iter into the factorial and wallis-pi procedures above to verify that they give the same results.

The similarities between our two versions of sum and product is no accident. This section of SICP is all about higher-order procedures, so in the next exercise we're going to see how pull the similarities out of these procedures into something even more abstract.


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.