Более эффективный муль-интервал


От 2.11

Упражнение 2.11. Мимоходом, Бен также загадочно комментарии: `путем тестирования признаки концы интервалы, можно сломать муль-интервал в девяти случаях только один которой требует более двух умножения". Переписать это процедуры с помощью предложения Бена.

Я написал следующее:

(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)))
           ))))


283
1
задан 4 апреля 2011 в 04:04 Источник Поделиться
Комментарии
1 ответ

Ваша логика правильная.

Вы можете использовать давай , а не давайте* поскольку стоимость одна привязка не зависит от значения другого привязки.

Поскольку эффективность является важным, вы можете сократить количество сравнений, а также. Например, если у-Х является отрицательным, то Л-Х тоже отрицательный и не должны быть проверены. По этой причине функции отрицательна?, положительный? и колеблется от нуля? не надо. Вместо этого вы можете просто использовать вложенные еслис:

(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
... ))

1
ответ дан 6 апреля 2011 в 11:04 Источник Поделиться