Exercise 2.11 of SICP

2009-07-27

sicp

Exercise 2.11: 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.

The assumption made here is that for any interval $$ [x_1,x_2] : x_1 \le x_2 $$

Using this assumption here are the 9 valid signs combinations.

[+,+] $ \cdot $ [+,+]
[+,+] $ \cdot $ [-,+]
[-,+] $ \cdot $ [-,+]
[-,+] $ \cdot $ [+,+]
[+,+] $ \cdot $ [-,-]
[-,-] $ \cdot $ [+,+]
[-,-] $ \cdot $ [-,+]
[-,+] $ \cdot $ [-,-]
[-,-] $ \cdot $ [-,-]

Notice that the case of 3 will need a little extra logic since it is possible for the two negative lower bounds to multiply together and become larger than the two positive upper bounds.

(define (mult-interval x y)
  (define (positive? a)
	(if (not (< a 0))
	  #t
	  #f))
  (define (negative? a)
	(if (not (< a 0))
	  #f
	  #t))
  (define (1-positives? a)
	(positive? a))
  (define (2-positives? a b)
	(and (positive? a) (positive? b)))
  (define (3-positives? a b c)
	(and (positive? a) 
		 (positive? b)
		 (positive? c)))
  (define (4-positives? a b c d)
	(and (positive? a) 
		 (positive? b)
		 (positive? c)
		 (positive? d)))
  (define (1-negatives? a)
	(not (1-positives? a)))
  (define (2-negatives? a b)
	(and (negative? a)
		 (negative? b)))
  (define (3-negatives? a b c)
	(and (negative? a)
		 (negative? b)
		 (negative? c)))
  (define (4-negatives? a b c d)
	(and (negative? a)
		 (negative? b)
		 (negative? c)
		 (negative? d)))
  (let ((x1 (lower-bound x))
		(x2 (upper-bound x))
		(y1 (lower-bound y))
		(y2 (upper-bound y)))
	(cond ((4-positives? x1 x2 y1 y2) (make-interval (* x1 y1) (* x2 y2))) ;1
		  ((4-negatives? x1 x2 y1 y2) (make-interval (* x2 y2) (* x1 y1))) ;9
		  ((and (3-positives? x1 x2 y2) ;2
				(1-negatives? y1))
			 (make-interval (* x2 y1) (* x2 y2)))
		  ((and (3-positives? x2 y1 y2) ;4
				(1-negatives? x1))
			 (make-interval (* x1 y2) (* x2 y2)))
		  ((and (3-negatives? x1 x2 y1) ;7
				(1-positives? y2))
		   (make-interval (* x1 y2) (* x1 y1)))
		  ((and (3-negatives? x1 y1 y2) ;8
				(1-positives? x2))
		   (make-interval (* x2 y1) (* x1 y1)))
		  ((and (2-positives? x1 x2) ;5
				(2-negatives? y1 y2))
		   (make-interval (* y1 x2) (* x1 y2)))
		  ((and (2-positives? y1 y2) ;6
				(2-negatives? x1 x2))
		   (make-interval (* x1 y2) (* y1 x2)))
		  ((and (2-positives? x2 y2) ;3
				(2-negatives? x1 y1))
		   (cond ((< x1 y1) (make-interval (* x1 y2) (* x2 y2)))
				 ((< y1 x1) (make-interval (* y1 x2) (* x2 y2))))))))

> (print (mul-interval (make-interval 1 2) (make-interval 3 4)))
[3,8] 
> (print (mult-interval (make-interval 1 2) (make-interval 3 4)))
[3,8] 
> (print (mult-interval (make-interval -2 -1) (make-interval -4 -3)))
[3,8] 
> (print (mul-interval (make-interval -2 -1) (make-interval -4 -3)))
[3,8] 
> (print (mul-interval (make-interval -2 1) (make-interval -4 -3)))
[-4,8] 
> (print (mult-interval (make-interval -2 1) (make-interval -4 -3)))
[-4,8]

I suspect this problem is given not because it’s an expert systems programmer’s way of solving it but for the interval arithmetic to sync in about always maximizing the width of the new interval whenever possible.

Contents