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

From Drewiki
Jump to: navigation, search

Problem

(This problem refers to Alyssa's interval arithmetic program from section 2.1.4 of the text.)

In passing, Ben also cryptically comments: "By testing the signs of the endpoints of the intervals, it is possible to break mul-interval into nine cases, only one of which requires more than two multiplications." Rewrite this procedure using Ben's suggestion.

Solution

Here's the original mul-interval implementation:

(define (make-interval a b) (cons a b))
 
(define (lower-bound i) (car i))
 
(define (upper-bound i) (cdr i))
 
(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))))

Given two intervals x and y, there are 4 endpoints: <math>x_1</math>, <math>x_2</math>, <math>y_1</math> and <math>y_2</math>. Each endpoint has two possible sign states: negative or positive (the latter including zero). Therefore, there are <math>2^4</math> combinations of endpoints, though some of them are impossible given our definition of intervals. Additionally, there are 4 possible products to consider for the endpoints of the interval resulting from the product of x and y: <math>x_1 y_1</math>, <math>x_1 y_2</math>, <math>x_2 y_1</math> and <math>x_2 y_2</math>.

Let's create a truth table that shows, for each input state, how to find the minimum and maximum value from the set of possible endpoints for the product of two intervals. Below the table is an explanation of each row.

In the following table, <math>+</math> means the endpoint is non-negative and <math>-</math> means the endpoint is negative. n/a means the input state is not valid, e.g., <math>x_1</math> is non-negative and <math>x_2</math> is negative; this state isn't possible because the definition of the interval is such that <math>x_1 \le x_2</math>. Each legal state is explained in detail below.

Interval multiplication state table
<math>x_1</math> <math>x_2</math> <math>y_1</math> <math>y_2</math> legal? min max
<math>-</math> <math>-</math> <math>-</math> <math>-</math> y <math>x_2 y_2</math> <math>x_1 y_1</math>
<math>-</math> <math>-</math> <math>-</math> <math>+</math> y <math>x_1 y_2</math> <math>x_1 y_1</math>
<math>-</math> <math>-</math> <math>+</math> <math>-</math> n n/a n/a
<math>-</math> <math>-</math> <math>+</math> <math>+</math> y <math>x_1 y_2</math> <math>x_2 y_1</math>
<math>-</math> <math>+</math> <math>-</math> <math>-</math> y <math>x_2 y_1</math> <math>x_1 y_2</math>
<math>-</math> <math>+</math> <math>-</math> <math>+</math> y ? ? *
<math>-</math> <math>+</math> <math>+</math> <math>-</math> n n/a n/a
<math>-</math> <math>+</math> <math>+</math> <math>+</math> y <math>x_1 y_2</math> <math>x_2 y_2</math>
<math>+</math> <math>-</math> <math>-</math> <math>-</math> n n/a n/a
<math>+</math> <math>-</math> <math>-</math> <math>+</math> n n/a n/a
<math>+</math> <math>-</math> <math>+</math> <math>-</math> n n/a n/a
<math>+</math> <math>-</math> <math>+</math> <math>+</math> n n/a n/a
<math>+</math> <math>+</math> <math>-</math> <math>-</math> y <math>x_2 y_1</math> <math>x_1 y_2</math>
<math>+</math> <math>+</math> <math>-</math> <math>+</math> y <math>x_2 y_1</math> <math>x_2 y_2</math>
<math>+</math> <math>+</math> <math>+</math> <math>-</math> n n/a n/a
<math>+</math> <math>+</math> <math>+</math> <math>+</math> y <math>x_1 y_1</math> <math>x_2 y_2</math>

As stated by Ben, there are in fact 9 possible cases. In 8 of the cases, we know the min and max endpoint products based solely on the signs of the endpoints. In the case marked with the asterisk (*), the signs do not provide enough information, so for this case we must calculate all 4 products and find the min and max, just like the original mul-interval procedure did.

Here is the (rather long) implementation of mul-interval that realizes this table. For compactness, we call non-negative numbers "positive" in this procedure. The else clause of the cond special form signals an illegal interval by returning zero. (This should never happen, of course, but it's useful to have a sanity check while testing such a complicated procedure to ensure we haven't missed a case.)

(define (mul-interval x y)
  (let ((x1 (lower-bound x))
        (x2 (upper-bound x))
        (y1 (lower-bound y))
        (y2 (upper-bound y))
        (x1-neg (> 0 (lower-bound x)))
        (x1-pos (<= 0 (lower-bound x)))
        (x2-neg (> 0 (upper-bound x)))
        (x2-pos (<= 0 (upper-bound x)))
        (y1-neg (> 0 (lower-bound y)))
        (y1-pos (<= 0 (lower-bound y)))
        (y2-neg (> 0 (upper-bound y)))
        (y2-pos (<= 0 (upper-bound y))))
    (cond ((and x1-neg x2-neg y1-neg y2-neg)
           (make-interval (* x2 y2) (* x1 y1)))
          ((and x1-neg x2-neg y1-neg y2-pos)
           (make-interval (* x1 y2) (* x1 y1)))
          ((and x1-neg x2-neg y1-pos y2-pos)
           (make-interval (* x1 y2) (* x2 y1)))
          ((and x1-neg x2-pos y1-neg y2-neg)
           (make-interval (* x2 y1) (* x1 y2)))
          ((and x1-neg x2-pos y1-pos y2-pos)
           (make-interval (* x1 y2) (* x2 y2)))
          ((and x1-pos x2-pos y1-neg y2-neg)
           (make-interval (* x2 y1) (* x1 y2)))
          ((and x1-pos x2-pos y1-neg y2-pos)
           (make-interval (* x2 y1) (* x2 y2)))
          ((and x1-pos x2-pos y1-pos y2-pos)
           (make-interval (* x1 y1) (* x2 y2)))
          ((and x1-neg x2-pos y1-neg y2-pos)
           (let ((p1 (* x1 y1))
                 (p2 (* x1 y2))
                 (p3 (* x2 y1))
                 (p4 (* x2 y2)))
             (make-interval (min p1 p2 p3 p4)
                            (max p1 p2 p3 p4))))
          (else 0))))

Here's the original mul-interval renamed so that we can use it to test the more complicated implementation.

(define (mul-interval-orig 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))))

Tests (not exhaustive!):

(define x1 (make-interval -1 3))
 
(define y1 (make-interval 3 7))
 
(lower-bound (mul-interval-orig x1 y1))

Output:

-7
(upper-bound (mul-interval-orig x1 y1))

Output:

21
(lower-bound (mul-interval x1 y1))

Output:

-7
(upper-bound (mul-interval x1 y1))

Output:

21
(define x2 (make-interval -4 -2))
 
(define y2 (make-interval -3 8))
 
(lower-bound (mul-interval-orig x2 y2))

Output:

-32
(upper-bound (mul-interval-orig x2 y2))

Output:

12
(lower-bound (mul-interval x2 y2))

Output:

-32
(upper-bound (mul-interval x2 y2))

Output:

12


Explanations of each row in the table

<math>x_1</math> <math>x_2</math> <math>y_1</math> <math>y_2</math> legal? min max
<math>-</math> <math>-</math> <math>-</math> <math>-</math> y <math>x_2 y_2</math> <math>x_1 y_1</math>

All endpoint products are non-negative because all input endpoints are negative. Then we know that

<math>\left|x_1\right| \ge \left|x_2\right|</math>

<math>\left|y_1\right| \ge \left|y_2\right|</math>

So the maximum endpoint product must be <math>x_1 y_1</math> and the minimum endpoint product must be <math>x_2 y_2</math>.


<math>x_1</math> <math>x_2</math> <math>y_1</math> <math>y_2</math> legal? min max
<math>-</math> <math>-</math> <math>-</math> <math>+</math> y <math>x_1 y_2</math> <math>x_1 y_1</math>

Products <math>x_1 y_1</math> and <math>x_2 y_1</math> are non-negative. Products <math>x_1 y_2</math> and <math>x_2 y_2</math> are negative. Then we know that

<math>x_1 y_1 > y_1 y_2</math>

<math>x_1 y_1 > x_2 y_2</math>

<math>x_2 y_1 > x_1 y_2</math>

<math>x_2 y_1 > x_2 y_2</math>

Additionally,

<math>\left|x_1\right| \ge \left|x_2\right|</math>

So the maximum endpoint product must be <math>x_1 y_1</math>, and the minimum endpoint product must be <math>x_1 y_2</math>, since the greater magnitude of <math>x_1</math> will make <math>x_1 y_2</math> "more negative" than <math>x_2 y_2</math>.


<math>x_1</math> <math>x_2</math> <math>y_1</math> <math>y_2</math> legal? min max
<math>-</math> <math>-</math> <math>+</math> <math>+</math> y <math>x_1 y_2</math> <math>x_2 y_1</math>

All endpoint products are negative. We also know that

<math>\left|x_1\right| \ge \left|x_2\right|</math>

So the maximum endpoint product must be <math>x_2 y_1</math>, since that product will be the "least negative" endpoint product, and the minimum endpoint product must be <math>x_1 y_2</math>, since that will be the "most negative" endpoint product.


<math>x_1</math> <math>x_2</math> <math>y_1</math> <math>y_2</math> legal? min max
<math>-</math> <math>+</math> <math>-</math> <math>-</math> y <math>x_2 y_1</math> <math>x_1 y_2</math>

Products <math>x_1 y_1</math> and <math>x_1 y_2</math> are non-negative. Products <math>x_2 y_1</math> and <math>x_2 y_2</math> are negative. Then we know that

<math>x_1 y_1 > x_2 y_1</math>

<math>x_1 y_1 > x_2 y_2</math>

<math>x_1 y_2 > x_2 y_1</math>

<math>x_1 y_2 > x_2 y_2</math>

Additionally,

<math>\left|y_1\right| > \left|y_2\right|</math>

So the maximum product must be <math>x_1 y_2</math>, and the minimum product must be <math>x_2 y_1</math>, since the greater magnitude of <math>y_1</math> will make <math>x_2 y_1</math> "more negative" than <math>x_2 y_2</math>.


<math>x_1</math> <math>x_2</math> <math>y_1</math> <math>y_2</math> legal? min max
<math>-</math> <math>+</math> <math>-</math> <math>+</math> y ? ? *

This is the only case in which we don't know the answer based solely on the signs of the endpoints. We have insufficient information because we don't know the relationship between the absolute values of <math>x_1</math> and <math>x_2</math>, and between <math>y_1</math> and <math>y_2</math>. For example, consider the following two cases:

  • x is the interval [-2, 1], y is the interval [-1, 2]. The max product is

<math>x_1 y_1 = 2</math>

and the min product is

<math>x_1 y_2 = -4</math>

  • x is the interval [-1, 2], y is the interval [-3, 2]. The max product is

<math>x_2 y_2 = 4</math>

and the min product is

<math>x_2 y_1 = -6</math>

The min and max products are different in each case.

For this case, we can just implement the multiplication the same way the original mul-interval procedure did: multiply out all 4 endpoint products and choose the max and min.


<math>x_1</math> <math>x_2</math> <math>y_1</math> <math>y_2</math> legal? min max
<math>-</math> <math>+</math> <math>+</math> <math>+</math> y <math>x_1 y_2</math> <math>x_2 y_2</math>

Products <math>x_2 y_1</math> and <math>x_2 y_2</math> are non-negative. Products <math>x_1 y_1</math> and <math>x_1 y_2</math> are negative. Then we know that

<math>x_2 y_1 > x_1 y_1</math>

<math>x_2 y_1 > x_1 y_2</math>

<math>x_2 y_2 > x_1 y_1</math>

<math>x_2 y_2 > x_1 y_2</math>

Also,

<math>x_2 y_2 > x_2 y_1</math>

since <math>y_2 > y_1</math>, and

<math>x_1 y_1 > x_1 y_2</math>

since <math>y_2 > y_1</math> but <math>x_1</math> is negative.

So the maximum product is <math>x_2 y_2</math> and the minimum product is <math>x_1 y_2</math>.


<math>x_1</math> <math>x_2</math> <math>y_1</math> <math>y_2</math> legal? min max
<math>+</math> <math>+</math> <math>-</math> <math>-</math> y <math>x_2 y_1</math> <math>x_1 y_2</math>

All products are negative. Also,

<math>\left|y_1\right| \ge \left|y_2\right|</math>

because <math>y_1</math> and <math>y_2</math> are negative. So the "most negative" product is <math>x_2 y_1</math> and the "least negative" product is <math>x_1 y_2</math>.


<math>x_1</math> <math>x_2</math> <math>y_1</math> <math>y_2</math> legal? min max
<math>+</math> <math>+</math> <math>-</math> <math>+</math> y <math>x_2 y_1</math> <math>x_2 y_2</math>

Products <math>x_1 y_1</math> and <math>x_2 y_1</math> are negative. Products <math>x_1 y_2</math> and <math>x_2 y_2</math> are non-negative. Then we know that

<math>x_1 y_2 > x_1 y_1</math>

<math>x_1 y_2 > x_2 y_1</math>

<math>x_2 y_2 > x_1 y_1</math>

<math>x_2 y_2 > x_2 y_1</math>

Also,

<math>x_1 y_1 > x_2 y_1</math>

since <math>x_2 > x_1</math> but <math>y_1</math> is negative. Then the "most negative" product is <math>x_2 y_1</math> and the maximum product is <math>x_2 y_2</math>.


<math>x_1</math> <math>x_2</math> <math>y_1</math> <math>y_2</math> legal? min max
<math>+</math> <math>+</math> <math>+</math> <math>+</math> y <math>x_1 y_1</math> <math>x_2 y_2</math>

All the endpoint products are non-negative. The minimum endpoint product is always the product of the minimum endpoints of the two intervals, and the maximum endpoint product is always the product of the maximum endpoints.

Personal tools