SICP exercise 2.08

From Drewiki

Problem

Using reasoning analogous to Alyssa's in section 2.1.4 of the text, describe how the difference of two intervals may be computed. Define a corresponding subtraction procedure, called sub-interval.

Solution

Here is the definition of add-interval as given in the text, along with the constructor and selectors we defined in exercise 2.7:

(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))
 
(define (make-interval a b) (cons a b))
 
(define (lower-bound i) (car i))
 
(define (upper-bound i) (cdr i))

Let's think about the difference between two intervals. Consider the difference $z = x - y$ of two intervals x and y, where

$x : \left [x_1, x_2 \right ], x_1 \le x_2$

$y : \left [y_1, y_2 \right ], y_1 \le y_2$ .

The bounds of interval z must be chosen from the set of differences

$\left \{x_1 - y_1, x_1 - y_2, x_2 - y_1, x_2 - y_2 \right \}$

Is one of these differences guaranteed always to be the minimum value of the set? The maximum value of the set?

Using some simple algebra on the inequalities, we can figure this out. For the minimum value, we know that $x_1 \le x_2$ . Subtracting $y 1$ from both sides of the inequality, we get

$x_1 - y_1 \le x_2 - y_1$

So we can eliminate $x 2 - y 1$ from the set of possible minimum values.

Repeat for $y 2$ :

$x_1 \le x_2$

$x_1 - y_2 \le x_2 - y_2$

and now we can eliminate $x 2 - y 2$ from the set of possible minimum values.

We also know that $y_1 \le y_2$ . Subtracting $y 1$ from both sides, we get

$0 \le y_2 - y_1$

Then, subtracting $y 2$ from both sides yields

$-y_2 \le -y_1$

Now add $x 1$ to both sides:

$x_1 - y_2 \le x_1 - y_1$

So now we can eliminate $x 1 - y 1$ from the set of possible minimum values, leaving only $x 1 - y 2$ . $x 1 - y 2$ is always the lower bound of the interval.

We already showed that

$x_1 - y_1 \le x_2 - y_1$ ,

so $x 1 - y 1$ is not the maximum value, nor is $x 1 - y 2$ , since that's the minimum value. We also showed that

$-y_2 \le - y_1$ ,

so by adding $x 2$ to both sides, we get

$x_2 - y_2 \le x_2 - y_1$

Therefore $x 2 - y 1$ must always be the upper bound of the interval.

Now we can define sub-interval:

(define (sub-interval x y)
  (make-interval (- (lower-bound x) (upper-bound y))
                 (- (upper-bound x) (lower-bound y))))

Test it:

(define i1 (make-interval 1 2))
 
(define i2 (make-interval 2 3))

The value of the expression (sub-interval i2 i1) should be the interval [0, 2], since if both values are at 2, the difference is 0 (the minimum value), and if i2 is at 3 and i1 is at 1, the difference is 2 (the maximum value). Let's check the procedure against our reasoning:

(lower-bound (sub-interval i2 i1))

Output:

(upper-bound (sub-interval i2 i1))

Output:

That looks good.

Now let's reverse the calculation: what is the value of (sub-interval i1 i2)? The minimum value in this case occurs when i1 is 1 and i2 is 3: then the value is -2. And the maximum value occurs when i1 is 2 and i2 is 2: then the value is 0.

Check again:

(lower-bound (sub-interval i1 i2))

Output:

-2

(upper-bound (sub-interval i1 i2))

Output:

Let's try two new intervals, one of which contains the other:

(define i3 (make-interval 1 2))
 
(define i4 (make-interval 0 4))

Subtracting interval i3 from interval i4, we should get the interval [-2, 3]. Let's check:

(lower-bound (sub-interval i4 i3))

Output:

-2

(upper-bound (sub-interval i4 i3))

Output:

Subtracting i4 from i3, we should get [-3, 2]:

(lower-bound (sub-interval i3 i4))

Output:

-3

(upper-bound (sub-interval i3 i4))

Output:

SICP exercise 2.08

From Drewiki

Problem

Solution

Views

Personal tools

Navigation

Search

Toolbox