SICP Exercise 1.31

2021-09-11

Question

1. The sum procedure is only the simplest of a vast number of similar abstractions that can be captured as higher-order procedures. 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 \(\pi\) using the formula

\[\frac{\pi}{4}=\frac{2\times 4\times 4\times 6\times 6\times 8\times \cdots}{3\times 3\times 5\times 5\times 7\times 7\times \cdots}\]

2. 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.

Answer

Here is my implementation of product. It’s very similar to sum, except that we return 1 instead of 0 for the base case (since that is the null operation for multiplication), and of course we multiply (term a) with the result of the recursive function call rather than adding it.

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

Next, let us define factorial using this function definition. For this, we utilise the same identity function we saw previously. Then we use the number 1 as the starting point and use inc for our next-function. This, then, simply multiplies all the numbers between 1 and x.

(define (identity x) x)

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

(factorial 6)

Result:

We could also use the Lambda-notation to avoid declaring the identity function.

(product (λ (i) i) 1 inc 6)

Next, we implement the approximation of \(\pi\) using this new algorithm:

(define (get_numerator n)
  (if (even? n) (+ n 2.0)
      (+ n 3.0)))

(define (get_denominator n)
  (if (even? n) (+ n 3.0)
      (+ n 2.0)))

(define (get_fraction n)
  (/ (get_numerator n) (get_denominator n)))

(define (approx_pi n)
  (* 4 (product get_fraction 0 inc n)))

(approx_pi 100)
(approx_pi 1000)
(approx_pi 10000)

As we see in the results, this gives quite a good estimate of \(\pi\), particularly as the number of iterations grows.

3.1263793980429804
3.1400269461050057
3.1414356249916424

Next, the second part of the question. Of course, our implementation of product above is recursive. So next, we will try implementing an iterative variant of the same algorithm.

For this, we can once again take inspiration from our previous implementation of sum which can be found in exercise 1.30. In fact, the only thing that needs to be changed (besides the procedure name of course) is the arithmetic operator + to *.

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

(product (λ (i) i) 1 inc 6)

And the output is as expected: