►zthomae’s SICP solutions
▼2 Chapter 2
2.1 Exercise 2.1
2.2 Exercise 2.2
2.3 Exercise 2.3
2.4 Exercise 2.4
2.5 Exercise 2.5
2.6 Exercise 2.6
2.7 Exercise 2.7
2.8 Exercise 2.8
2.9 Exercise 2.9
2.10 Exercise 2.10
2.11 Exercise 2.11
2.12 Exercise 2.12
2.13 Exercise 2.13
2.14 Exercise 2.14
2.15 Exercise 2.15
2.16 Exercise 2.16
2.17 Exercise 2.17
2.18 Exercise 2.18
2.19 Exercise 2.19
2.20 Exercise 2.20
2.21 Exercise 2.21
2.22 Exercise 2.22
2.23 Exercise 2.23
2.24 Exercise 2.24
2.25 Exercise 2.25
2.26 Exercise 2.26
2.27 Exercise 2.27
2.28 Exercise 2.28
2.29 Exercise 2.29
2.30 Exercise 2.30
2.31 Exercise 2.31
2.32 Exercise 2.32
2.33 Exercise 2.33
2.34 Exercise 2.34
2.35 Exercise 2.35
2.36 Exercise 2.36
2.37 Exercise 2.37
2.38 Exercise 2.38
2.39 Exercise 2.39
2.40 Exercise 2.40
2.41 Exercise 2.41
2.42 Exercise 2.42
2.43 Exercise 2.43
2.44 Exercise 2.44
2.45 Exercise 2.45
2.46 Exercise 2.46
2.47 Exercise 2.47
2.48 Exercise 2.48
2.49 Exercise 2.49
2.50 Exercise 2.50
2.51 Exercise 2.51
2.52 Exercise 2.52
2.53 Exercise 2.53
2.54 Exercise 2.54
2.55 Exercise 2.55
2.56 Exercise 2.56
2.57 Exercise 2.57
2.58 Exercise 2.58
2.59 Exercise 2.59
2.60 Exercise 2.60
2.61 Exercise 2.61
2.62 Exercise 2.62
2.63 Exercise 2.63
2.64 Exercise 2.64
2.65 Exercise 2.65
2.66 Exercise 2.66
2.67 Exercise 2.67
2.68 Exercise 2.68
2.69 Exercise 2.69
2.70 Exercise 2.70
2.71 Exercise 2.71
2.72 Exercise 2.72
2.73 Exercise 2.73
2.74 Exercise 2.74
2.75 Exercise 2.75
2.76 Exercise 2.76
2.77 Exercise 2.77
2.78 Exercise 2.78
2.79 Exercise 2.79
2.80 Exercise 2.80
2.81 Exercise 2.81
2.82 Exercise 2.82
2.83 Exercise 2.83
2.84 Exercise 2.84
2.85 Exercise 2.85
2.86 Exercise 2.86
2.87 Exercise 2.87
2.88 Exercise 2.88
2.89 Exercise 2.89
2.90 Exercise 2.90
2.91 Exercise 2.91
2.92 Exercise 2.92
2.93 Exercise 2.93
2.94 Exercise 2.94
2.95 Exercise 2.95
2.96 Exercise 2.96
2.97 Exercise 2.97
    ← prev  up  next → 

2.11 Exercise 2.11

Ben’s point is that there are nine different valid sign combinations for the lower and upper bounds of the two intervals being multiplied, and that a basic application of inequalities can will show that the bounds of the new interval are, in all cases except one, knowable directly, without having to get the min or max of a group of possible bounds. Making the new mul-interval procedure is not hard, but it is tedious and easy to make mistakes. Therefore, we will make a basic testing procedure to make sure that our new procedure agrees with the existing mul-interval for all sign combinations.

First, a useful procedure that should already have been defined, for determining if two intervals are the same:

(define (equal-intervals? x y)
  (and
   (= (lower-bound x) (lower-bound y))
   (= (upper-bound x) (upper-bound y))))

We can use this to test if multiplied intervals by two different procedures are equal. Applying this to every combination of signs for the bounds of two intervals (whose bounds are chosen arbitrarily, and should not be important), we can make a procedure to exhaustively test the nine sign combination cases to make sure that our new procedure gets the same result as the old one every time.

(define (test-new-mul-interval new-mul-interval)
  (define (equal-products? x y)
    (equal-intervals? (mul-interval x y) (new-mul-interval x y)))
  (define (neg x) (* x -1))
  (let ((lx 1)
        (ux 10)
        (ly 2)
        (uy 4))
    (cond
      ((not (equal-products?
             (make-interval lx ux) (make-interval ly uy)))
       (error "new-mul-interval fails for lx > 0, ux > 0, ly > 0, uy > 0"))
      ((not (equal-products?
             (make-interval lx ux) (make-interval (neg ly) uy)))
       (error "new-mul-interval fails for lx > 0, ux > 0, ly < 0, uy > 0"))
      ((not (equal-products?
             (make-interval lx ux) (make-interval (neg ly) (neg uy))))
       (error "new-mul-interval fails for lx > 0, ux > 0, ly < 0, uy < 0"))
      ((not (equal-products?
             (make-interval (neg lx) ux) (make-interval ly uy)))
       (error "new-mul-interval fails for lx < 0, ux > 0, ly > 0, uy > 0"))
      ((not (equal-products?
             (make-interval (neg lx) ux) (make-interval (neg ly) uy)))
       (error "new-mul-interval fails for lx < 0, ux > 0, ly < 0, uy > 0"))
      ((not (equal-products?
             (make-interval (neg lx) ux) (make-interval (neg ly) (neg uy))))
       (error "new-mul-interval fails for lx < 0, ux > 0, ly < 0, uy < 0"))
      ((not (equal-products?
             (make-interval (neg lx) (neg ux)) (make-interval ly uy)))
       (error "new-mul-interval fails for lx < 0, ux < 0, ly > 0, uy > 0"))
      ((not (equal-products?
             (make-interval (neg lx) (neg ux)) (make-interval (neg ly) uy)))
       (error "new-mul-interval fails for lx < 0, ux < 0, ly < 0, uy > 0"))
      ((not (equal-products?
             (make-interval (neg lx) (neg ux)) (make-interval (neg ly) (neg uy))))
       (error "new-mul-interval fails for lx < 0, ux < 0, ly < 0, uy < 0"))
      (else #t))))

The code is not pretty, but it works, and will pinpoint exactly what cases are in error. I made mistakes when I first wrote the new multiplication procedure, and this was helpful.

Below is the new multiplication procedure using a reduced number of multiplications. It uses a cond statement checking combinations of signs for all bounds (and as a stylistic choice, leaves the case with more than 2 multiplications for the else case).

(define (mul-interval-ben x y)
  (let ((lx (lower-bound x))
        (ux (upper-bound x))
        (ly (lower-bound y))
        (uy (upper-bound y)))
    (cond
      ((and (> lx 0) (> ux 0) (> ly 0) (> uy 0))
       (make-interval (* lx ly) (* ux uy)))
      ((and (> lx 0) (> ux 0) (< ly 0) (> uy 0))
       (make-interval (* ux ly) (* ux uy)))
      ((and (> lx 0) (> ux 0) (< ly 0) (< uy 0))
       (make-interval (* ux uy) (* lx ly)))
      ((and (< lx 0) (> ux 0) (> ly 0) (> uy 0))
       (make-interval (* lx uy) (* ux uy)))
      ((and (< lx 0) (> ux 0) (< ly 0) (< uy 0))
       (make-interval (* ux uy) (* lx uy)))
      ((and (< lx 0) (< ux 0) (> ly 0) (> uy 0))
       (make-interval (* ux uy) (* lx ly)))
      ((and (< lx 0) (< ux 0) (< ly 0) (> uy 0))
       (make-interval (* ux uy) (* ux ly)))
      ((and (< lx 0) (< ux 0) (< ly 0) (< uy 0))
       (make-interval (* lx ly) (* ux uy)))
      (else
       (make-interval (min (* lx uy) (* ux ly))
                      (max (* lx ly) (* ux uy)))))))

And using our testing procedure, we can verify that this procedure is correct:

> (test-new-mul-interval mul-interval-ben)

#t

    ← prev  up  next →