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

From Drewiki
Jump to: navigation, search


Explain, in general, why equivalent algebraic expressions may lead to different answers. Can you devise an interval-arithmetic package that does not have this shortcoming, or is this task impossible? (Warning: This problem is very difficult.)


In the interval arithmetic system we've defined, some of the laws of algebra that we're accustomed to don't apply to certain operations, so algebraic expressions that are equivalent in a non-interval arithmetic system are not necessarily equivalent in an interval arithmetic system.

For example, consider the distributive law. The distributive law states that

<math> a(b+c) = ab+ac </math>

but this law does not universally apply in our interval arithmetic system. Here's an example:

(define (make-interval a b) (cons a b))
(define (lower-bound i) (car i))
(define (upper-bound i) (cdr i))
(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))
(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 a (make-interval 2 4))
(define b (make-interval -2 0))
(define c (make-interval 3 8))
(define x (mul-interval a
                        (add-interval b c)))
(define y (add-interval (mul-interval a b)
                        (mul-interval a c)))
(lower-bound x)



(upper-bound x)



(lower-bound y)



(upper-bound y)



So the expression <math>a(b+c)</math> evaluates to the interval [2,32] and the expression <math>ab+ac</math> evaluates to the interval [-2,32]. Which one is "correct"? Are both?

There are other algebraic laws that fail in our system as well: try squaring the interval [-2,2], for example.

There are many pitfalls in designing an interval arithmetic system. I'm not sure whether it's possible to devise an interval arithmetic system that overcomes these problems, but there is a lot of documentation and research about interval arithmetic here:

Here is a fairly accessible paper that gives a high-level overview of interval arithmetic, including why it's important and what some of the problems are (including the ones we've discussed in some of these exercises):

And here is a technical paper which describes a constrained interval arithmetic in which the distributive law (and several other algebraic laws) applies:

Personal tools