SICP 연습문제 2.11 친절한 풀이

문제

또, Ben은 지나가다가 살짝 귀띔하기를 '구간 양 끝점의 부호가 어떻게 되는지 검사하면, mul-interval 프로시저는 계산하는 방법을 아홉 가지 경우로 나타낼 수 있는데, 그 중에 두 번 이상 곱셈 할 일은 한 번밖에 없다’고 한다. Ben이 제안한대로 mul-interval 프로시저를 다시 짜보라.

문제로 부터 얻은 것

특별히 얻은 것은 없습니다. 각각의 경우의 수를 구현하는 것이 귀찮았습니다.

문제풀이

문제를 보면, 구간 양 끝점의 부호를 알면 경우의 수를 아홉가지로 줄일 수 있다고 합니다.
이 말이 참말인지 한번 알아보도록 하겠습니다.
하나의 구간은 세가지 경우로 나뉠 수 있습니다.

1. 양 끝점이 둘 다 양수인 경우 (pospos)
2. 하한값은 음수고 상한값은 양수인 경우 (appo)
3. 양 끝점이 둘 다 음수인 경우 (negneg)

하나의 구간이 3가지 경우의 수로 나뉘므로
2개의 구간을 곱셈연산하는 것은 $3×3=9$의 경우의 수로 나눌 수 있습니다.
이를 define과 cond를 이용해 9가지의 경우의 수를 표현하면 아래와 같습니다.

(define (pos? x)
  (or (> x 0) (= x 0)))

(define (neg? x)
  (< x 0))
  
(define (pospos? z)
  (and (pos? (lower-bound z)) (pos? (upper-bound z))))
(define (negpos? z)
  (and (neg? (lower-bound z)) (pos? (upper-bound z))))
(define (negneg? z)
  (and (neg? (lower-bound z)) (neg? (upper-bound z))))

(cond 
  ((and (pospos? x) (pospos? y)))
  ((and (pospos? x) (negpos? y)))
  ((and (pospos? x) (negneg? y)))
  ((and (negpos? x) (pospos? y)))
  ((and (negpos? x) (negpos? y)))
  ((and (negpos? x) (negneg? y)))
  ((and (negneg? x) (pospos? y)))
  ((and (negneg? x) (negpos? y)))
  ((and (negneg? x) (negneg? y))))

각각의 경우에 맞는 곱셈 결과를 cond문에 추가해서 프로시저를 완성시키겠습니다.

(define (mul-interval x y)
  (define (pospos? z)
    (and (pos? (lower-bound z)) (pos? (upper-bound z))))
  (define (negpos? z)
    (and (neg? (lower-bound z)) (pos? (upper-bound z))))
  (define (negneg? z)
    (and (neg? (lower-bound z)) (neg? (upper-bound z))))
  
  (cond 
    ((and (pospos? x) (pospos? y))
     (make-interval (* (lower-bound x) (lower-bound y))
                    (* (upper-bound x) (upper-bound y))))
    ((and (pospos? x) (negpos? y))
     (make-interval (* (upper-bound x) (lower-bound y))
                    (* (upper-bound x) (upper-bound y))))
    ((and (pospos? x) (negneg? y))
     (make-interval (* (upper-bound x) (lower-bound y))
                    (* (lower-bound x) (upper-bound y))))
    ((and (negpos? x) (pospos? y))
     (make-interval (* (lower-bound x) (upper-bound y))
                    (* (upper-bound x) (upper-bound y))))
    ((and (negpos? x) (negpos? y))
     (make-interval (min (* (lower-bound x) (upper-bound y))
                         (* (upper-bound x) (lower-bound y)))
                    (max (* (lower-bound x) (lower-bound y))
                         (* (upper-bound x) (upper-bound y)))))
    ((and (negpos? x) (negneg? y))
     (make-interval (* (upper-bound x) (lower-bound y))
                    (* (lower-bound x) (lower-bound y))))
    ((and (negneg? x) (pospos? y))
     (make-interval (* (lower-bound x) (upper-bound y))
                    (* (upper-bound x) (lower-bound y))))
    ((and (negneg? x) (negpos? y))
     (make-interval (* (lower-bound x) (upper-bound y))
                    (* (lower-bound x) (lower-bound y))))
    ((and (negneg? x) (negneg? y))
     (make-interval (* (upper-bound x) (upper-bound y))
                    (* (lower-bound x) (lower-bound y))))))

문제에서 말한 두번 이상 곱셈을 해야 하는 경우는 x와 y 둘다 음수 하한값과 양수 상한값을 가질 때입니다.
이 경우 하한끼리 곱한 값과 상한 끼리 곱한 값 중 어떤 것이 더 클지는 알 수 없기 때문입니다.

읽어주셔서 감사합니다.