SICP Exercise 2.9: Interval Widths

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.

Let's begin by defining a procedure for calculating an interval's width:

(define (interval-width i)
  (/ (- (upper-bound i) (lower-bound i)) 2))

Given this definition we can show by substitution that the width of any interval produced by evaluating add-interval or sub-interval with any two argument intervals is a function of the widths of the argument intervals. To do this, let's first assume that we have four values, l1, l2, u1 and u2 such that l1<u1 and l2<u2. Then we define two intervals, i1 and i2, as follows:

(define i1 (make-interval l1 u1))
(define i2 (make-interval l2 u2))

We can first of all produce expressions for their widths by substitution as follows:

  (interval-width i1)
= (/ (- (upper-bound i1) (lower-bound i1)) 2)
= (/ (- (max (car i1) (cdr i1)) (min (car i1) (cdr i1))) 2)
= (/ (- (max l1 u1) (min l1 u1)) 2)
= (/ (- u1 l1) 2)

  (interval-width i2)
= (/ (- (upper-bound i2) (lower-bound i2)) 2)
= (/ (- (max (car i2) (cdr i2)) (min (car i2) (cdr i2))) 2)
= (/ (- (max l2 u2) (min l2 u2)) 2)
= (/ (- u2 l2) 2)

Now let's see what happens when we try to calculate the width of the interval produced by evaluating the expression (add-interval i1 i2):

  (interval-width (add-interval i1 i2))
= (interval-width (make-interval (+ (lower-bound i1) (lower-bound i2))
                                 (+ (upper-bound i1) (upper-bound i2))))
= (interval-width (make-interval (+ (min (car i1) (cdr i1)) (min (car i2) (cdr i2)))
                                 (+ (max (car i1) (cdr i1)) (max (car i2) (cdr i2)))))
= (interval-width (make-interval (+ (min l1 u1) (min l2 u2))
                                 (+ (max l1 u1) (max l2 u2))))
= (interval-width (make-interval (+ (min l1 u1) (min l2 u2))
                                 (+ (max l1 u1) (max l2 u2))))
= (interval-width (make-interval (+ l1 l2) (+ u1 u2)))
= (interval-width (cons (+ l1 l2) (+ u1 u2)))
= (/ (- (upper-bound (cons (+ l1 l2) (+ u1 u2)))
        (lower-bound (cons (+ l1 l2) (+ u1 u2)))) 2)
= (/ (- (+ u1 u2) (+ l1 l2)) 2)
≡ (/ (+ (- u1 l1) (- u2 l2)) 2)
≡ (+ (/ (- u1 l1) 2) (/ (- u2 l2) 2))
≡ (+ (interval-width i1) (interval-width i2))

So we can see that the width of the interval produced by evaluating the expression (add-interval i1 i2) is the sum of the widths of intervals i1 and i2.

We can try to calculate the width of the interval produced by evaluating the expression (sub-interval i1 i2) in the same way:

  (interval-width (sub-interval i1 i2))
= (interval-width (make-interval (- (lower-bound i1) (upper-bound i2))
                                 (- (upper-bound i1) (lower-bound i2))))
= (interval-width (make-interval (- (min (car i1) (cdr i1)) (max (car i2) (cdr i2)))
                                 (- (max (car i1) (cdr i1)) (min (car i2) (cdr i2)))))
= (interval-width (make-interval (- (min l1 u1) (max l2 u2))
                                 (- (max l1 u1) (min l2 u2))))
= (interval-width (make-interval (- l1 u2) (- u1 l2)))
= (interval-width (cons (- l1 u2) (- u1 l2)))
= (/ (- (upper-bound (cons (- l1 u2) (- u1 l2)))
        (lower-bound (cons (- l1 u2) (- u1 l2)))) 2)
= (/ (- (- u1 l2) (- l1 u2)) 2)
≡ (/ (+ (- u1 l1) (- u2 l2)) 2)
≡ (+ (/ (- u1 l1) 2) (/ (- u2 l2) 2))
≡ (+ (interval-width i1) (interval-width i2))

Similarly we can see that the width of the interval produced by evaluating the expression (sub-interval i1 i2) is also the sum of the widths of intervals i1 and i2.

Let's check these both seem to hold:

> (define i1 (make-interval 3 9))
> (define i2 (make-interval 4 14))
> (interval-width i1)
3
> (interval-width i2)
5
> (interval-width (add-interval i1 i2))
8
> (interval-width (sub-interval i1 i2))
8

For the last part of this exercise we're asked to show that this isn't true for multiplication or division by providing examples. Now we could just stick our intervals from above into the interpreter and claim that this shows that there's no sensible function here:

> (interval-width (mul-interval i1 i2))
57
> (interval-width (div-interval i1 i2))
1.0178571428571428

But this doesn't prove anything. For all we know it may be the case that:

  (interval-width (mul-interval i1 i2))
≡ (+ (* (interval-width i1) 2) (* (interval-width i2) 10) 1)

and:

  (interval-width (div-interval i1 i2))
≡ (/ (+ (* (interval-width i1) 2) (* (interval-width i2) 10) 1.0)
     (+ (* (interval-width i1) 2) (* (interval-width i2) 10)))

However, while these expressions give the same results for the intervals, i1 and i2, we defined above, they're not actually equivalent expressions, and wouldn't work for other intervals. If you're not convinced, try just swapping the intervals around in the expressions.

Let's instead prove it by substitution again. Note that the interval produced by mul-interval can be different combinations of the bounds of the two intervals passed to it depending upon which of the set of values {p1, p2, p3, p4} are the maximum and minimum. Let's assume that l1 and l2 are integer values >1 (which implies that u1 and u2 are too). This means that p1 (the value of the expression (* l1 l2)) will be the minimum and p4 (the value of the expression (* u1 u2)) will be the maximum. Given that assumption, here's what we get when we try to calculate the width of the interval produced by evaluating the expression (mul-interval i1 i2):

  (interval-width (mul-interval i1 i2))
= (interval-width
    (let ((p1 (* (lower-bound i1) (lower-bound i2)))
          (p2 (* (lower-bound i1) (upper-bound i2)))
          (p3 (* (upper-bound i1) (lower-bound i2)))
          (p4 (* (upper-bound i1) (upper-bound i2))))
      (make-interval (min p1 p2 p3 p4)
                     (max p1 p2 p3 p4)))
= (interval-width
    (let ((p1 (* (min (car i1) (cdr i1)) (min (car i2) (cdr i2))))
          (p2 (* (min (car i1) (cdr i1)) (max (car i2) (cdr i2))))
          (p3 (* (max (car i1) (cdr i1)) (min (car i2) (cdr i2))))
          (p4 (* (max (car i1) (cdr i1)) (max (car i2) (cdr i2)))))
      (make-interval (min p1 p2 p3 p4)
                     (max p1 p2 p3 p4)))
= (interval-width
    (let ((p1 (* (min l1 u1) (min l2 u2)))
          (p2 (* (min l1 u1) (max l2 u2)))
          (p3 (* (max l1 u1) (min l2 u2)))
          (p4 (* (max l1 u1) (max l2 u2))))
      (make-interval (min p1 p2 p3 p4)
                     (max p1 p2 p3 p4)))
= (interval-width
    (let ((p1 (* l1 l2))
          (p2 (* l1 u2))
          (p3 (* u1 l2))
          (p4 (* u1 u2)))
      (make-interval (min p1 p2 p3 p4)
                     (max p1 p2 p3 p4)))
= (interval-width
    (make-interval (min (* l1 l2) (* l1 u2) (* u1 l2) (* u1 u2))
                   (max (* l1 l2) (* l1 u2) (* u1 l2) (* u1 u2))))
= (interval-width (make-interval (* l1 l2) (* u1 u2)))
= (interval-width (cons (* l1 l2) (* u1 u2)))
= (/ (- (upper-bound (cons (* l1 l2) (* u1 u2)))
        (lower-bound (cons (* l1 l2) (* u1 u2))))
     2)
= (/ (- (* u1 u2) (* l1 l2)) 2)

Now it is not possible to convert this expression to an equivalent expression that consists of terms of (interval-width i1), (interval-width i2) and constants alone. As a result, it is not possible to express the width of multiplying two arbitrary intervals in terms of the widths of those intervals.

Let's do division now... Using the same assumption as above, here's what we get when we try to calculate the width of the interval produced by evaluating the expression (div-interval i1 i2):

  (interval-width (div-interval i1 i2))
= (interval-width
    (mul-interval i1
                  (make-interval (/ 1.0 (upper-bound i2))
                                 (/ 1.0 (lower-bound i2)))))
= (interval-width (mul-interval i1 (make-interval (/ 1.0 u2) (/ 1.0 l2))))
= (interval-width (mul-interval i1 (cons (/ 1.0 u2) (/ 1.0 l2))))
= (interval-width
    (let ((p1 (* (lower-bound i1) (lower-bound (cons (/ 1.0 u2) (/ 1.0 l2)))))
          (p2 (* (lower-bound i1) (upper-bound (cons (/ 1.0 u2) (/ 1.0 l2)))))
          (p3 (* (upper-bound i1) (lower-bound (cons (/ 1.0 u2) (/ 1.0 l2)))))
          (p4 (* (upper-bound i1) (upper-bound (cons (/ 1.0 u2) (/ 1.0 l2))))))
      (make-interval (min p1 p2 p3 p4)
                     (max p1 p2 p3 p4)))

At this point we should note that, as l2 is the lower bound of interval i2, and u2 the upper bound, constructing an interval with the reciprocals of these two bounds with mean that (/ 1.0 l2) is the upper bound and (/ 1.0 u2) is the lower bound. So:

  (interval-width
    (let ((p1 (* (lower-bound i1) (lower-bound (cons (/ 1.0 u2) (/ 1.0 l2)))))
          (p2 (* (lower-bound i1) (upper-bound (cons (/ 1.0 u2) (/ 1.0 l2)))))
          (p3 (* (upper-bound i1) (lower-bound (cons (/ 1.0 u2) (/ 1.0 l2)))))
          (p4 (* (upper-bound i1) (upper-bound (cons (/ 1.0 u2) (/ 1.0 l2))))))
      (make-interval (min p1 p2 p3 p4)
                     (max p1 p2 p3 p4)))
= (interval-width
    (let ((p1 (* l1 (/ 1.0 u2)))
          (p2 (* l1 (/ 1.0 l2)))
          (p3 (* u1 (/ 1.0 u2)))
          (p4 (* u1 (/ 1.0 l2))))
      (make-interval (min p1 p2 p3 p4)
                     (max p1 p2 p3 p4)))
≡ (interval-width
    (let ((p1 (/ l1 u2))
          (p2 (/ l1 l2))
          (p3 (/ u1 u2))
          (p4 (/ u1 l2)))
      (make-interval (min p1 p2 p3 p4)
                     (max p1 p2 p3 p4)))
= (interval-width
    (make-interval (min (/ l1 u2) (/ l1 l2) (/ u1 u2) (/ u1 l2))
                   (max (/ l1 u2) (/ l1 l2) (/ u1 u2) (/ u1 l2))))
= (interval-width (make-interval (/ l1 u2) (/ u1 l2)))
= (interval-width (cons (/ l1 u2) (/ u1 l2)))
= (/ (- (upper-bound  (cons (/ l1 u2) (/ u1 l2)))
        (lower-bound (cons (/ l1 u2) (/ u1 l2))))
     2)
= (/ (- (/ u1 l2) (/ l1 u2)) 2)

Again it is not possible to convert this expression to an equivalent expression that consists of terms of (interval-width i1), (interval-width i2) and constants alone, and so it is also not possible to express the width of dividing two arbitrary intervals in terms of the widths of those intervals.