一种更有效的多间隔

Question

来自2.11

练习2.11。顺便说一句，Ben还含糊其辞地评论道：通过测试区间端点的符号，可以将多个区间分解为九种情况，其中一种只需要两次以上的乘法。用本的建议重写这个程序。

我写了以下文章：

(define (negative? . n) (or (= 0 (length n))
                            (and (> 0 (car n)) (apply negative? (cdr n)))))

(define (positive? . n) (or (= 0 (length n))
                            (and (>= (car n) 0) (apply positive? (cdr n)))))

(define (straddles-zero? x) (and (>= 0 (lower-bound x))
                                 (>= (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)))))))

你认为如何？

新版本如下：

(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 ((> l-x 0) 
           ;x > 0
           (cond ((> l-y 0)
                  ;y > 0
                  (make-interval (* l-x l-y) (* u-x u-y))
                  )
                 ((< u-y 0)
                  ;y < 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))
                  ))
           )
          ((> l-y 0)
           ;y > 0
           (if (< u-x 0)
               ; x < 0
               (make-interval (* u-y l-x) (* l-y u-x))
               ; x contains 0
               (make-interval (* l-x u-y) (* u-x l-y))
               )
           )
          ((< u-x 0)
           ;x < 0
           (if (< u-y 0)
               ; y < 0
               (make-interval (* u-x u-y) (* l-x l-y))
               ; y contains 0
               (make-interval (* u-y u-x) (* l-y u-x))
               )
           )
          ((< u-y 0)
           ;y < 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)))
           ))))

Answer 1

你的逻辑是正确的。

您可以使用let而不是let*，因为一个绑定的值不取决于另一个绑定的值。

因为效率很重要，所以你也可以减少比较的次数。例如，如果u-x是阴性的，那么l-x也是阴性的，不需要测试。因此，negative?、positive?和straddles-zero?函数是不必要的。相反，只需使用嵌套的ifs：

(if (< u-x 0)
    ; x is in R < 0
    (if (< u-y 0)
        ; y is in R < 0
        ...
        (if (< l-y 0)
            ; y contains 0
            ...
            ; y is in R >= 0
            ... ))
    (if (< l-x 0)
        ; x contains 0
        ...
        ; x is in R >= 0
        ... ))