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 2.09

From Drewiki
Jump to: navigation, search

Problem

The width of an interval is half of the difference between its upper and lower bounds. The width is a measure of the uncertainty of the number specified by the interval. For some arithmetic operations the width of the result of combining two intervals is a function only of the widths of the argument intervals, whereas for others the width of the combination is not a function of the widths of the argument intervals. Show that the width of the sum (or difference) of two intervals is a function only of the widths of the intervals being added (or subtracted). Give examples to show that this is not true for multiplication or division.

Solution

Here's the definition of the procedure add-interval:

(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))

Where x and y are two intervals defined by

<math>x : \left [x_1, x_2 \right ], x_1 \le x_2</math>

<math>y : \left [y_1, y_2 \right ], y_1 \le y_2</math>

We can also define an interval using an alternate representation: the pair (m, w), where w is the width of the interval and m is its midpoint. The same two intervals x and y defined above using the original representation are defined like so using this alternate representation:

<math>x : \left (x_m, x_w \right), x_w = \frac{x_2 - x_1}{2}, x_m = x_1 + x_w</math>

<math>y : \left (y_m, y_w \right ), y_w = \frac{y_2 - y_1}{2}, y_m = y_1 + y_w</math>

Let z be the sum of x and y. Using the original representation, z is defined by

<math>z : \left [x_1 + y_1, x_2 + y_2 \right ]</math>

The width of z is

<math>\begin{align}

z_w & = \frac{x_2 + y_2 - x_1 - y_1}{2} \\
    & = \frac{x_2 - x_1}{2} + \frac{y_2 - y_1}{2} \\
    & = x_w + y_w

\end{align} </math>

In the answer to exercise 2.8, we proved that the interval <math>z = x - y</math> is

<math>z : \left [x_1 - y_2, x_2 - y_1 \right ]</math>

Then

<math>\begin{align} z_w & = \frac{x_1 - y_2 - x_2 + y_1}{2} \\

   & = \frac{x_1 - x_2}{2} + \frac{y_1 - y_2}{2} \\
   & = -x_w + -y_w

\end{align} </math>

Therefore, the width of the sum of two intervals, and the width of the difference of two intervals, is a function only of the widths of the two intervals.

The exercise also asks us to give examples to show that it isn't true that the width of the resulting interval is a function of the widths of the operands for multiplication and division.

Let's use Scheme procedures to demonstrate. Below, interval x1 and interval x2 have width 1, and intervals y1 and y2 have width 2. However, the product of x1 and y1 does not have the same width as the product of x2 and y2; nor does y1/x1 have the same width as y2/x2.

(define (make-interval a b) (cons a b))
 
(define (lower-bound i) (car i))
 
(define (upper-bound i) (cdr i))
 
(define (interval-width i)
  (/ (- (upper-bound i)
        (lower-bound i))
     2))
 
(define (mul-interval x y)
  (let ((p1 (* (lower-bound x) (lower-bound y)))
        (p2 (* (lower-bound x) (upper-bound y)))
        (p3 (* (upper-bound x) (lower-bound y)))
        (p4 (* (upper-bound x) (upper-bound y))))
    (make-interval (min p1 p2 p3 p4)
                   (max p1 p2 p3 p4))))
 
(define (div-interval x y)
  (mul-interval x
                (make-interval (/ 1.0 (upper-bound y))
                               (/ 1.0 (lower-bound y)))))
 
(define x1 (make-interval 2 4))
 
(define x2 (make-interval 3 5))
(interval-width x1)

Output:

1
(interval-width x2)

Output:

1
(define y1 (make-interval 1 5))
 
(define y2 (make-interval 3 7))
 
(interval-width y1)

Output:

2
(interval-width y2)

Output:

2
(interval-width (mul-interval x1 y1))

Output:

9
(interval-width (mul-interval x2 y2))

Output:

13
(interval-width (div-interval y1 x1))

Output:

1.125
(interval-width (div-interval y2 x2))

Output:

0.866666666666666
Personal tools