A more efficient mul-interval From 2.11


  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.


I wrote the following:

(define (negative? . n) (or (= 0 (length n))
                            (and (&gt; 0 (car n)) (apply negative? (cdr n)))))

(define (positive? . n) (or (= 0 (length n))
                            (and (&gt;= (car n) 0) (apply positive? (cdr n)))))

(define (straddles-zero? x) (and (&gt;= 0 (lower-bound x))
                                 (&gt;= (upper-bound x) 0)))

(define (fast-mul-interval x y)
  (let* ((u-x (upper-bound x))
        (u-y (upper-bound y))
        (l-x (lower-bound x))
        (l-y (lower-bound y)))
    (cond 
      ; same sign - max is neg, or min is pos
      ((positive? l-y l-x) (make-interval (* l-x l-y) (* u-x u-y)))
      ((negative? u-y u-x) (make-interval (* u-x u-y) (* l-x l-y)))
      ; x and y have opposite signs
      ((and (positive? l-x) 
            (negative? u-y)) (make-interval (* u-x l-y) (* l-x u-y)))
      ((and (positive? l-y)
            (negative? u-x)) (make-interval (* l-x u-y) (* u-x l-y)))

      ; x straddles zero
      ((straddles-zero? x)
       (if (straddles-zero? y)
           (make-interval (min (* l-x u-y) (* l-y u-x)) 
                          (max (* l-x l-y) (* u-x u-y)))
           (if (negative? u-y)
               (make-interval (* u-x l-y) (* l-x l-y))
               (make-interval (* l-x u-y) (* u-x u-y)))))
      ((straddles-zero? y)
       (if (negative? u-x)
           (make-interval (* u-y l-x) (* l-y l-x))
           (make-interval (* l-y u-x) (* u-y u-x)))))))


What do you think?



The new version is here:

(define (fast-mul-interval x y)
  (let ((l-x (lower-bound x))
        (u-x (upper-bound x))
        (l-y (lower-bound y))
        (u-y (upper-bound y)))
    (cond ((&gt; l-x 0) 
           ;x &gt; 0
           (cond ((&gt; l-y 0)
                  ;y &gt; 0
                  (make-interval (* l-x l-y) (* u-x u-y))
                  )
                 ((&lt; u-y 0)
                  ;y &lt; 0
                  (make-interval (* u-x l-y) (* l-x u-y))
                  )
                 (else
                  ;y contains 0
                  (make-interval (* u-x l-y) (* u-y u-x))
                  ))
           )
          ((&gt; l-y 0)
           ;y &gt; 0
           (if (&lt; u-x 0)
               ; x &lt; 0
               (make-interval (* u-y l-x) (* l-y u-x))
               ; x contains 0
               (make-interval (* l-x u-y) (* u-x l-y))
               )
           )
          ((&lt; u-x 0)
           ;x &lt; 0
           (if (&lt; u-y 0)
               ; y &lt; 0
               (make-interval (* u-x u-y) (* l-x l-y))
               ; y contains 0
               (make-interval (* u-y u-x) (* l-y u-x))
               )
           )
          ((&lt; u-y 0)
           ;y &lt; 0 and x contains 0
           (make-interval (* u-y u-x) (* l-x u-y))
           )
          (else 
           ;x and y both contain 0
           (let ((p1 (* l-x l-y))
                 (p2 (* l-x u-y))
                 (p3 (* u-x u-y))
                 (p4 (* u-x l-y)))
             (make-interval (min p1 p2 p3 p4) (max p1 p2 p3 p4)))
           ))))
Your logic is correct.

You may use let instead of let* since the value of one binding does not depend on the value of another binding.

Since efficiency is important, you can cut back on the number of comparisons as well.  For example, if u-x is negative, then l-x is also negative and need not be tested.  For this reason, the functions negative?, positive? and straddles-zero? are not necessary.  Instead, you can simply use nested ifs:

(if (&lt; u-x 0)
    ; x is in R &lt; 0
    (if (&lt; u-y 0)
        ; y is in R &lt; 0
        ...
        (if (&lt; l-y 0)
            ; y contains 0
            ...
            ; y is in R &gt;= 0
            ... ))
    (if (&lt; l-x 0)
        ; x contains 0
        ...
        ; x is in R &gt;= 0
        ... ))