sicp-ex-2.8



<< Previous exercise (2.7) | Index | Next exercise (2.9) >>


jz

  
 ;; ex 2.8 
  
 ;; The max and min can be supplied to the constructor in any order. 
 (define (make-interval a b) (cons a b)) 
 (define (upper-bound interval) (max (car interval) (cdr interval))) 
 (define (lower-bound interval) (min (car interval) (cdr interval))) 
  
 ;; The minimum value would be the smallest possible value 
 ;; of the first minus the largest of the second.  The maximum would be 
 ;; the largest of the first minus the smallest of the second. 
 (define (sub-interval x y) 
   (make-interval (- (lower-bound x) (upper-bound y)) 
                  (- (upper-bound x) (lower-bound y)))) 
  
 (define (display-interval i) 
   (newline) 
   (display "[") 
   (display (lower-bound i)) 
   (display ",") 
   (display (upper-bound i)) 
   (display "]")) 
  
 ;; Usage 
 (define i (make-interval 2 7)) 
 (define j (make-interval 8 3)) 
  
 (display-interval i) 
 (display-interval (sub-interval i j)) 
 (display-interval (sub-interval j i)) 
  

shyam

Specifying subtraction in terms of addition is more accurate.

We also have the example of division specified in terms of multiplication in the text

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

Where add-interval as given in the text is :

 (define (add-interval x y) 
   (make-interval (+ (lower-bound x) (lower-bound y)) 
                  (+ (upper-bound x) (upper-bound y)))) 

This even works for negative valued interval, whether or not , we want to use values in that range ;-)

Here are some examples:

1 ]=> (sub-interval (make-interval 4 5) (make-interval 1 2))

;Value 27: (2 . 4)

1 ]=> (sub-interval (make-interval (- 4) (- 5)) (make-interval 1 2))

;Value 28: (-7 . -5)

1 ]=> (sub-interval (make-interval 4 5) (make-interval (- 1) 2))

;Value 29: (2 . 6)

1 ]=> (sub-interval (make-interval 4 5) (make-interval 1 (- 2)))

;Value 30: (3 . 7)

1 ]=> (sub-interval (make-interval (- 4) 5) (make-interval 1 2))

;Value 31: (-6 . 4)

1 ]=> (sub-interval (make-interval 4 (- 5)) (make-interval 1 2))

;Value 32: (-7 . 3)

1 ]=> 

> This even works for negative valued interval, whether or not , we want to use values in that range ;-)

The proposed solution works for negative values as well. The minimum of two intervals is always (- (lower a) (upper b)), and the maximum is always (- (upper a) (lower b)).

Otherwise, though, you are correct; it certainly is more elegant to define subtraction in terms of addition.



rj1094

The above solutions are incorrect. To work correctly with ex 2.9, this width of the first interval minus the second interval must equal the width of the result of sub-interval.

So the resulting interval's lower bound is defined by subtracting the lower bounds of the inputs, and vice-versa for the upper bound:

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

The above solutions are not incorrect, take a look at the following excerpt from ex 2.9:

Show that the width of the sum (or difference) of two intervals is a function only of the widths of the intervals being added (or subtracted)

Confusion might arise because it seems the exercise implies that:

  • the sum of widths must be the widths of the intervals being added
  • the difference of widths must be the widths of the intervals being subtracted

But that is not true, added (or subtracted) is being presented as a possibility which must be proven, rather than a correlation between the sum and the difference.

In any case, perhaps the following example can prove useful in understanding operations with intervals.

Subtracting two intervals a and b is the same as adding a and the opposite of b (as shown in the above solution by shyam), getting the opposite of an interval implies getting the opposites of its lower and upper bounds and swapping them.

Consider an interval with lower bound 1 and upper bound 3: [1, 3] Writing it as an inequality:

1 <= x <= 3

(x is any possible value in this range)

The opposite of this interval can be obtained by multiplying all of its members by (-1)

1(-1) <= x(-1) <= 3(-1)

-1 <= -x <= -3

This yields a untrue statement since x cant be simultaneously greater than -1 and less than -3, this would require -1 < -3 to be true, which is impossible since negative numbers get greater as they approach 0. This requires an additional step: the inequality relation must be reversed, and consequently, its lower and upper bounds will be reversed:

 -1 <= -x <= -3 (impossible statement) 
  
 Reversed relations: 
  
 -1 >= -x >= -3 
  
 Which is the same as: 
  
 -3 <= -x <= -1 

The opposite of the interval [1, 3] is [-3, -1]. Notice that adding [-3, -1] to another interval a would be the same as subtracting [1, 3] from a with the above solutions:

(sub-interval a [1, 3]) equals (add-interval a [-3, -1])

IMHO this explanation is a bit lengthy and also doesn't show "the difference of widths must be the widths of the intervals being subtracted" or "... being added".

[a1,b1]-[a2,b2]=[a1-b2,b1-a2]. So the width of the result is (b1-a2)-(a1-b2)=(b1-a1)+(b2-a2). So it should be "... being added" instead of what rj1094 says.

---

In a summary, for any operation on 2 intervals. We just think about how we can get the lower/upper bound when choosing 1 number from each interval and doing the operation on them. This works for all operations.

Then it is straightforward to choose the lower bound of minuend and the upper bound of subtractor for the lower bound of the result, similarly for the upper bound of the result.




Hammer

For those confused as to why when subtracting an interval you take a lower bound from x and an upper bound from y (and vice versa), consider that subtraction is addition with a negated second term; and that when a higher-bound is negated, it will become a lower-bound (and vice versa). To demonstrate, this intuitive solution produces equivalent results to (- lower-bound higher-bound) despite not specifying that.

  
 ;; ex 2.8 
  
 (define (lower-bound  interval) (min (car interval) (cdr interval))) 
 (define (upper-bound  interval) (max (car interval) (cdr interval))) 
  
 (define (negate-interval interval) 
   (make-interval (* -1 (lower-bound interval)) (* -1 (upper-bound interval)))) 
  
 (define (add-interval x y) 
   (make-interval (+ (lower-bound x) (lower-bound y)) 
                  (+ (upper-bound x) (upper-bound y)))) 
  
 (define (sub-interval x y) 
   (let ((y (negate-interval y))) 
     (add-interval x y))) 
  
equivalent results to (- lower-bound higher-bound)

More clearly it says about the lower bound of the result. Here `(lower-bound y)` will choose the correct smaller number to add.