Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 1.31

From Drewiki
Jump to: navigation, search

This exercise has two parts.

Contents

Problem A

The sum procedure given in the text 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 <math>\pi</math> using the formula

<math> \frac{\pi}{4}=\frac{2\cdot4\cdot4\cdot6\cdot6\cdot8\cdot\cdot\cdot}{3\cdot3\cdot5\cdot5\cdot7\cdot7\cdot\cdot\cdot}</math>

Solution A

Here's an iterative product procedure, defined nearly identically to the iterative sum procedure from exercise 1.30:

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

And here's factorial defined in terms of product:

(define (inc n) (+ n 1))
 
(define (factorial n)
  (define (identity n) n)
  (product identity 1 inc n))

Now some tests:

(factorial 1)

Output:

1
(factorial 2)

Output:

2
(factorial 3)

Output:

6
(factorial 4)

Output:

24
(factorial 5)

Output:

120
(factorial 6)

Output:

720


That looks good.

Here's a procedure which calculates an approximation for <math>\pi</math> using n terms of the sequence given above:

(define (approximate-pi n)
  (define (numerator n)
    (if (even? n)
        (+ n 2)
        (+ n 3)))
  (define (denominator n)
    (if (even? n)
        (+ n 3)
        (+ n 2)))
  (* (/ (product numerator 0 inc (- n 1))
        (product denominator 0 inc (- n 1)))
     4))

And some tests, using Chicken Scheme 3.1 on a MacBook Pro running Mac OS X 10.5:

(approximate-pi 100)

Output:

3.15703017645517
(approximate-pi 150)

Output:

3.15194378082968


Note that there's a problem with this implementation of approximate-pi on many Schemes. For example, here are the results of evaluating a few more combinations, again using Chicken Scheme 3.1 on a MacBook Pro running Mac OS X 10.5:

(approximate-pi 169)

Output:

3.13242017902291
(approximate-pi 170)

Output:

+nan


That last result, +nan, means that while evaluating the combination (approximate-pi 170), the result of the calculation exceeded the range of the number representation (most likely the representation provided by the hardware's floating-point registers). Moreover, the last value it produces before running out of range isn't even a good approximation of <math>\pi</math>.

The reason there's a problem in this particular execution environment is that the two products that compose the numerator and denominator of the fraction in the computation increase monotonically with n. When n > 169, one or both of those products exceeds the range of the number representation, they're "rounded up" to infinity, and the computation produces "not-a-number" when it attempts to operate on an infinite value.

A Scheme which implements infinite-precision arithmetic, such as MIT/GNU Scheme, does not have this limitation, and could evaluate this procedure for increasingly large values of n, given sufficient time and space to do so. However, this feature might come at a performance cost: such a Scheme implementation might be significantly slower than Chicken Scheme for some values of n < 170 due to the nature of its infinite-precision number representation.

Here's an alternative definition of approximate-pi that works for much larger values of n on limited-numeric-precision Schemes such as Chicken Scheme:

(define (approximate-pi n)
  (define (numerator n)
    (if (even? n)
        (+ n 2)
        (+ n 3)))
  (define (denominator n)
    (if (even? n)
        (+ n 3)
        (+ n 2)))
  (define (term n)
    (/ (numerator n) (denominator n)))
  (* (product term 0 inc (- n 1))
     4))

This version calculates only a single product, dividing each term in the sequence prior to accumulating it, rather than accumulating separate numerator and divisor products and dividing them at the end of the computation. Let's test it on the same Chicken Scheme setup:

(approximate-pi 169)

Output:

3.1324201790229
(approximate-pi 170)

Output:

3.15073842568385
(approximate-pi 171)

Output:

3.13252606484175


It works for n = 170 and n = 171. In fact, it works for very large values of n, each producing a more accurate result (and taking more time to compute). Here are the results from my Chicken Scheme setup:

(approximate-pi 1000)

Output:

3.14316070553226
(approximate-pi 10000)

Output:

3.14174970573801
(approximate-pi 100000)

Output:

3.14160836127794
(approximate-pi 1000000)

Output:

3.14159422438285


The reason this definition works for values of n where the previous definition does not is because the running total of the product is always very close to the value <math>\pi/4</math>. Each successive term gets us closer to the actual value, rather than monotonically increasing per the previous definition.

However, this version has some problems, too. The hardware registers used by Chicken Scheme to perform the computation not only have limited range, they also have limited precision (see exercise 1.7). Each term of the product generated by this second version of approximate-pi is a fraction, and some of them cannot be represented exactly in the floating-point hardware, either because they're irrational numbers or because their number of significant digits exceeds the precision of the hardware. Each such term introduces a small error into the computation, and as we're accumulating the product as we go, the errors accumulate, too. So this version of the procedure may be less accurate than the original, since the latter avoids errors due to irrational and/or limited precision numbers until nearly the last step (the final / operator).

Additionally, the second version may be slower than the first. On circa-2008 hardware (and traditionally, as well), multiplication operations are significantly faster than division operations. The process generated by evaluating the first implementation of approximate-pi performs roughly 2n multiplications, and only a single division. However, the process generated by the second performs n multiplications and n divisions, since each term of the product is a quotient. Therefore, the second implementation is practically guaranteed to be slower than the first.

Problem B

If your product procedure generates a recursive process, write one that generates an iterative process, and vice versa.

Solution B

The definition of product given in Solution A above is iterative, so here's a recursive implementation:

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

Tests:

(factorial 1)

Output:

1
(factorial 2)

Output:

2
(factorial 3)

Output:

6
(factorial 4)

Output:

24
(factorial 5)

Output:

120
(factorial 6)

Output:

720
Personal tools