Solution to SICP Exercise 2.9

Structure and Interpretation of Computer Programs

A solution to Exercise 2.9:

Some preliminary definitions:

(upper-bound (make-interval a b)) = a [1]
(lower-bound (make-interval a b)) = b [2]

(width i) = (/ (- (upper-bound i) (lower-bound i)) 2) [3]

(add i1 i2) = (make-interval (+ (upper-bound i1) (upper-bound i2))
(+ (lower-bound i1) (lower-bound i2))) [4]

Rearranging [3]:

(* 2 (width i)) = (- (upper-bound i) (lower-bound i))
(+ (* 2 (width i)) (lower-bound i)) = (upper-bound i) [5]

From [3]:

(width (add i1 i2)) = (/ (- (upper-bound (add i1 i2))
(lower-bound (add i1 i2)))
2)

Simplifying with [1], [2] and [4]:

(width (add i1 i2)) = (/ (- (+ (upper-bound i1)
(upper-bound i2))
(+ (lower-bound i1)
(lower-bound i2)))
2)

Substituting in [5]:

= (/ (- (+ (+ (* 2 (width i1)) (lower-bound i1))
(+ (* 2 (width i2)) (lower-bound i2)))
(+ (lower-bound i1)
(lower-bound i2)))
2)

= (/ (- (+ (* 2 (width i1)) (* 2 (width i2))
(lower-bound i1)
(lower-bound i2))
(+ (lower-bound i1)
(lower-bound i2)))
2)

All the (lower-bound x)s cancel out, leaving:

= (/ (+ (* 2 (width i1))
(* 2 (width i2)))
2)

So do the 2s:

(width (add i1 i2)) = (+ (width i1) (width i2))

Clearly the width of the sum is a function only of the width of the operands.

Advertisements