計算機プログラムの構造と解釈 第二版 P53 問題2.11

やることは、

・Benが言っているように手続きを書き直す。

Benがそもそもなにを狙っているかというと、
今まで使っていた、mul-intervalはmaxとかminをつかって、
最小値と最大値を出していて結構ずるっこい。
だけど、これをちゃんと整理して作り直しましょうよ、
ってこと。

区間の掛け算(mul-interval)について考える。
Ben曰く、各区間の符号を考えると9つあると。

なるほど、たとえば、区間 xとyがあったとする。
xl:xの下限値
xu:xの上限値
yl:yの下限値
yu:yの上限値

端点(上限値か下限値)を意識してみると。
xl >= 0 (xの下限値が、0より大きい場合)(xlもxuも0か正の数)
xu <= 0 (xの上限値が、0より小さい場合)(xlもxuも0か負の数)
xが0に跨がる場合 (xuが正の数で、xlが負の数)
の三つに分けられそうだし、
yもまた、
yl >= 0 (yの下限値が、0より大きい場合)(ylもyuも0か正の数)
yu <= 0 (yの上限値が、0より小さい場合)(ylもyuも0か負の数)
yが0に跨がる場合 (yuが正の数で、ylが負の数)
だ。

そうすると、mul-intervalの結果の中身は

           |    yl >= 0　  |    yu <= 0	   | yl<0, yu>0	
-----------+---------------+---------------+----------------
xl >= 0    | (xlyl . xuyu) | (xuyl . xlyu) | (xuyl . xuyu)
xu <= 0    | (xlyu . xuyl) | (xuyu . xlyu) | (xlyu . xlyl)
xl<0, xu>0 | (xlyu . xuyu) | (xuyl . xlyl) | min(xlyu, xuyl), max(xlyl, xuyu)

なんて感じでケース別にわけられるよねぇ。

あとは粛々と実装するのみ。
以下実装

#!/usr/local/bin/gosh
;; -*- coding: utf-8 -*-

(use ggc.debug.trace)
(use math.mt-random)

;;積
(define (mul-interval x y)
  (let ((p1 (* (lower-bound x) (lower-bound y)))
        (p2 (* (lower-bound x) (upper-bound y)))
        (p3 (* (upper-bound x) (lower-bound y)))
        (p4 (* (upper-bound x) (upper-bound y))))
    (make-interval (min p1 p2 p3 p4) 
                   (max p1 p2 p3 p4))))

;;interval
(define (make-interval a b) (cons a b)) 

(define upper-bound cdr)
(define lower-bound car)


;;問題2-11
(define (mul-interval2 x y)
  (let ((xl (lower-bound x)) 
        (xu (upper-bound x)) 
        (yl (lower-bound y)) 
        (yu (upper-bound y)))
    (cond ((>= xl 0)
           (cond ((>= yl 0) (make-interval (* xl yl) (* xu yu)))
                 ((<= yu 0) (make-interval (* xu yl) (* xl yu)))
                 (else
                   (make-interval (* xu yl) (* xu yu)))))
          ((<= xu 0)
           (cond ((>= yl 0) (make-interval (* xl yu) (* xu yl)))
                 ((<= yu 0) (make-interval (* xu yu) (* xl yl)))
                 (else
                   (make-interval (* xl yu) (* xl yl)))))
          (else
            (cond ((>= yl 0) (make-interval (* xl yu) (* xu yu)))
                  ((<= yu 0) (make-interval (* xu yl) (* xl yl)))
                  (else
                    (make-interval (min (* xl yu) (* xu yl)) (max (* xl yl) (* xu yu)))))))))


(define intervalx1 (make-interval 3 5))
(define intervalx2 (make-interval -6 -2))
(define intervalx3 (make-interval -4 2))
(define intervaly1 (make-interval 4 7))
(define intervaly2 (make-interval -8 -1))
(define intervaly3 (make-interval -3 3))



;; main
(define (main args)

  (newline)
  
  (display "intervalx1: ")
  (display intervalx1)
  (newline)
  (display "intervalx2: ")
  (display intervalx2)
  (newline)
  (display "intervalx3: ")
  (display intervalx3)
  (newline)
  (display "intervaly1: ")
  (display intervaly1)
  (newline)
  (display "intervaly2: ")
  (display intervaly2)
  (newline)
  (display "intervaly3: ")
  (display intervaly3)
  (newline)(newline)


  (display "xl >= 0の時 ")(newline)
  (display "且つ yl >= 0の時 ")(newline)
  (display "(mul-interval intervalx1 intervaly1): ")
  (display (mul-interval intervalx1 intervaly1))
  (newline)
  (display "(mul-interval2 intervalx1 intervaly1): ")
  (display (mul-interval2 intervalx1 intervaly1))
  (newline)
  (display "且つ yu <= 0の時 ")(newline)
  (display "(mul-interval intervalx1 intervaly2): ")
  (display (mul-interval intervalx1 intervaly2))
  (newline)
  (display "(mul-interval2 intervalx1 intervaly2): ")
  (display (mul-interval2 intervalx1 intervaly2))
  (newline)
  (display "且つ yl<0, yu>0の時 ")(newline)
  (display "(mul-interval intervalx1 intervaly3): ")
  (display (mul-interval intervalx1 intervaly3))
  (newline)
  (display "(mul-interval2 intervalx1 intervaly3): ")
  (display (mul-interval2 intervalx1 intervaly3))
  (newline)(newline)

  (display "xu <= 0の時 ")(newline)
  (display "且つ yl >= 0の時 ")(newline)
  (display "(mul-interval intervalx2 intervaly1): ")
  (display (mul-interval intervalx2 intervaly1))
  (newline)
  (display "(mul-interval2 intervalx2 intervaly1): ")
  (display (mul-interval2 intervalx2 intervaly1))
  (newline)
  (display "且つ yu <= 0の時 ")(newline)
  (display "(mul-interval intervalx2 intervaly2): ")
  (display (mul-interval intervalx2 intervaly2))
  (newline)
  (display "(mul-interval2 intervalx2 intervaly2): ")
  (display (mul-interval2 intervalx2 intervaly2))
  (newline)
  (display "且つ yl<0, yu>0の時 ")(newline)
  (display "(mul-interval intervalx2 intervaly3): ")
  (display (mul-interval intervalx2 intervaly3))
  (newline)
  (display "(mul-interval2 intervalx2 intervaly3): ")
  (display (mul-interval2 intervalx2 intervaly3))
  (newline)(newline)

  (display "xl<0, xu>0の時 ")(newline)
  (display "且つ yl >= 0の時 ")(newline)
  (display "(mul-interval intervalx2 intervaly1): ")
  (display (mul-interval intervalx2 intervaly1))
  (newline)
  (display "(mul-interval2 intervalx2 intervaly1): ")
  (display (mul-interval2 intervalx2 intervaly1))
  (newline)
  (display "且つ yu <= 0の時 ")(newline)
  (display "(mul-interval intervalx2 intervaly2): ")
  (display (mul-interval intervalx2 intervaly2))
  (newline)
  (display "(mul-interval2 intervalx2 intervaly2): ")
  (display (mul-interval2 intervalx2 intervaly2))
  (newline)
  (display "且つ yl<0, yu>0の時 ")(newline)
  (display "(mul-interval intervalx2 intervaly3): ")
  (display (mul-interval intervalx2 intervaly3))
  (newline)
  (display "(mul-interval2 intervalx2 intervaly3): ")
  (display (mul-interval2 intervalx2 intervaly3))
  (newline)(newline)

  (newline)
0)

実行

intervalx1: (3 . 5)
intervalx2: (-6 . -2)
intervalx3: (-4 . 2)
intervaly1: (4 . 7)
intervaly2: (-8 . -1)
intervaly3: (-3 . 3)

xl >= 0の時 
且つ yl >= 0の時 
(mul-interval intervalx1 intervaly1): (12 . 35)
(mul-interval2 intervalx1 intervaly1): (12 . 35)
且つ yu <= 0の時 
(mul-interval intervalx1 intervaly2): (-40 . -3)
(mul-interval2 intervalx1 intervaly2): (-40 . -3)
且つ yl<0, yu>0の時 
(mul-interval intervalx1 intervaly3): (-15 . 15)
(mul-interval2 intervalx1 intervaly3): (-15 . 15)

xu <= 0の時 
且つ yl >= 0の時 
(mul-interval intervalx2 intervaly1): (-42 . -8)
(mul-interval2 intervalx2 intervaly1): (-42 . -8)
且つ yu <= 0の時 
(mul-interval intervalx2 intervaly2): (2 . 48)
(mul-interval2 intervalx2 intervaly2): (2 . 48)
且つ yl<0, yu>0の時 
(mul-interval intervalx2 intervaly3): (-18 . 18)
(mul-interval2 intervalx2 intervaly3): (-18 . 18)

xl<0, xu>0の時 
且つ yl >= 0の時 
(mul-interval intervalx2 intervaly1): (-42 . -8)
(mul-interval2 intervalx2 intervaly1): (-42 . -8)
且つ yu <= 0の時 
(mul-interval intervalx2 intervaly2): (2 . 48)
(mul-interval2 intervalx2 intervaly2): (2 . 48)
且つ yl<0, yu>0の時 
(mul-interval intervalx2 intervaly3): (-18 . 18)
(mul-interval2 intervalx2 intervaly3): (-18 . 18)

おけ。