SICP exercise 2.11

From Drewiki

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: $x 1$ , $x 2$ , $y 1$ and $y 2$ . Each endpoint has two possible sign states: negative or positive (the latter including zero). Therefore, there are $24$ 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: $x 1 y 1$ , $x 1 y 2$ , $x 2 y 1$ and $x 2 y 2$ .

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, $+$ means the endpoint is non-negative and $-$ means the endpoint is negative. n/a means the input state is not valid, e.g., $x 1$ is non-negative and $x 2$ is negative; this state isn't possible because the definition of the interval is such that $x_1 \le x_2$ . Each legal state is explained in detail below.

**Interval multiplication state table**
$x 1$	$x 2$	$y 1$	$y 2$	legal?	min	max
$-$	$-$	$-$	$-$	y	$x 2 y 2$	$x 1 y 1$
$-$	$-$	$-$	$+$	y	$x 1 y 2$	$x 1 y 1$
$-$	$-$	$+$	$-$	n	n/a	n/a
$-$	$-$	$+$	$+$	y	$x 1 y 2$	$x 2 y 1$
$-$	$+$	$-$	$-$	y	$x 2 y 1$	$x 1 y 2$
$-$	$+$	$-$	$+$	y	?	? *
$-$	$+$	$+$	$-$	n	n/a	n/a
$-$	$+$	$+$	$+$	y	$x 1 y 2$	$x 2 y 2$
$+$	$-$	$-$	$-$	n	n/a	n/a
$+$	$-$	$-$	$+$	n	n/a	n/a
$+$	$-$	$+$	$-$	n	n/a	n/a
$+$	$-$	$+$	$+$	n	n/a	n/a
$+$	$+$	$-$	$-$	y	$x 2 y 1$	$x 1 y 2$
$+$	$+$	$-$	$+$	y	$x 2 y 1$	$x 2 y 2$
$+$	$+$	$+$	$-$	n	n/a	n/a
$+$	$+$	$+$	$+$	y	$x 1 y 1$	$x 2 y 2$

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:

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

Output:

-7

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

Output:

(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:

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

Output:

-32

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

Output:

Explanations of each row in the table

$x 1$	$x 2$	$y 1$	$y 2$	legal?	min	max
$-$	$-$	$-$	$-$	y	$x 2 y 2$	$x 1 y 1$

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

$\left|x_1\right| \ge \left|x_2\right|$

$\left|y_1\right| \ge \left|y_2\right|$

So the maximum endpoint product must be $x 1 y 1$ and the minimum endpoint product must be $x 2 y 2$ .

$x 1$	$x 2$	$y 1$	$y 2$	legal?	min	max
$-$	$-$	$-$	$+$	y	$x 1 y 2$	$x 1 y 1$

Products $x 1 y 1$ and $x 2 y 1$ are non-negative. Products $x 1 y 2$ and $x 2 y 2$ are negative. Then we know that

$x 1 y 1 > y 1 y 2$

$x 1 y 1 > x 2 y 2$

$x 2 y 1 > x 1 y 2$

$x 2 y 1 > x 2 y 2$

Additionally,

$\left|x_1\right| \ge \left|x_2\right|$

So the maximum endpoint product must be $x 1 y 1$ , and the minimum endpoint product must be $x 1 y 2$ , since the greater magnitude of $x 1$ will make $x 1 y 2$ "more negative" than $x 2 y 2$ .

$x 1$	$x 2$	$y 1$	$y 2$	legal?	min	max
$-$	$-$	$+$	$+$	y	$x 1 y 2$	$x 2 y 1$

All endpoint products are negative. We also know that

$\left|x_1\right| \ge \left|x_2\right|$

So the maximum endpoint product must be $x 2 y 1$ , since that product will be the "least negative" endpoint product, and the minimum endpoint product must be $x 1 y 2$ , since that will be the "most negative" endpoint product.

$x 1$	$x 2$	$y 1$	$y 2$	legal?	min	max
$-$	$+$	$-$	$-$	y	$x 2 y 1$	$x 1 y 2$

Products $x 1 y 1$ and $x 1 y 2$ are non-negative. Products $x 2 y 1$ and $x 2 y 2$ are negative. Then we know that

$x 1 y 1 > x 2 y 1$

$x 1 y 1 > x 2 y 2$

$x 1 y 2 > x 2 y 1$

$x 1 y 2 > x 2 y 2$

Additionally,

$\left|y_1\right| > \left|y_2\right|$

So the maximum product must be $x 1 y 2$ , and the minimum product must be $x 2 y 1$ , since the greater magnitude of $y 1$ will make $x 2 y 1$ "more negative" than $x 2 y 2$ .

$x 1$	$x 2$	$y 1$	$y 2$	legal?	min	max
$-$	$+$	$-$	$+$	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 $x 1$ and $x 2$ , and between $y 1$ and $y 2$ . For example, consider the following two cases:

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

$x 1 y 1 = 2$

and the min product is

$x 1 y 2 = - 4$

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

$x 2 y 2 = 4$

and the min product is

$x 2 y 1 = - 6$

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.

$x 1$	$x 2$	$y 1$	$y 2$	legal?	min	max
$-$	$+$	$+$	$+$	y	$x 1 y 2$	$x 2 y 2$

Products $x 2 y 1$ and $x 2 y 2$ are non-negative. Products $x 1 y 1$ and $x 1 y 2$ are negative. Then we know that

$x 2 y 1 > x 1 y 1$

$x 2 y 1 > x 1 y 2$

$x 2 y 2 > x 1 y 1$

$x 2 y 2 > x 1 y 2$

Also,

$x 2 y 2 > x 2 y 1$

since $y 2 > y 1$ , and

$x 1 y 1 > x 1 y 2$

since $y 2 > y 1$ but $x 1$ is negative.

So the maximum product is $x 2 y 2$ and the minimum product is $x 1 y 2$ .

$x 1$	$x 2$	$y 1$	$y 2$	legal?	min	max
$+$	$+$	$-$	$-$	y	$x 2 y 1$	$x 1 y 2$

All products are negative. Also,

$\left|y_1\right| \ge \left|y_2\right|$

because $y 1$ and $y 2$ are negative. So the "most negative" product is $x 2 y 1$ and the "least negative" product is $x 1 y 2$ .

$x 1$	$x 2$	$y 1$	$y 2$	legal?	min	max
$+$	$+$	$-$	$+$	y	$x 2 y 1$	$x 2 y 2$

Products $x 1 y 1$ and $x 2 y 1$ are negative. Products $x 1 y 2$ and $x 2 y 2$ are non-negative. Then we know that

$x 1 y 2 > x 1 y 1$

$x 1 y 2 > x 2 y 1$

$x 2 y 2 > x 1 y 1$

$x 2 y 2 > x 2 y 1$

Also,

$x 1 y 1 > x 2 y 1$

since $x 2 > x 1$ but $y 1$ is negative. Then the "most negative" product is $x 2 y 1$ and the maximum product is $x 2 y 2$ .

$x 1$	$x 2$	$y 1$	$y 2$	legal?	min	max
$+$	$+$	$+$	$+$	y	$x 1 y 1$	$x 2 y 2$

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.

SICP exercise 2.11

From Drewiki

Problem

Solution

Explanations of each row in the table

Views

Personal tools

Navigation

Search

Toolbox