Edited at

SICP読書録 #20 2.1.4 発展問題:区間演算

hiroshi-manabe様の日本語訳を使わせてもらいます。

練習問題等はGaucheで実行。

前回はこちら


2.1.4 発展問題:区間演算

例えば、「10%の許容誤差で6.8Ω」という抵抗の抵抗値は 6.12 〜 7.48Ω (6.8 ± 0.68Ω) となる。こうした「区間」に対する演算を行えるようにしよう。

区間オブジェクトをadd-interval手続きで生成でき、上限値と下限値をそれぞれupper-bound,lower-bound手続きで得られるとすると、足し算、掛け算、割り算は次のように定義できる。


_.scm

(define (add-interval x y)

(make-interval (+ (lower-bound x) (lower-bound y))
(+ (upper-bound x) (upper-bound y))))

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

(define (div-interval x y)
(mul-interval
x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y)))))



練習問題 2.7

make-interval,upper-bound,lower-boundを定義。


_.scm

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

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


練習問題 2.8

add-intervalと同様の考え方で、引き算sub-intervalを定義しよう。

$c_x\pm{w_x}$ と $c_y\pm{w_y}$ を加算した結果は $(c_x+c_y)\pm(w_x+w_y)$。

そこで、引き算の結果は $(c_x-c_y)\pm(w_x+w_y)$ となるようにしてみよう。

下限値は $(c_x-w_x)-(c_y+w_y)$、上限値は $(c_x+w_x)-(c_y-w_y)$ と計算できる。


_.scm

(define (sub-interval x y)

(make-interval (- (lower-bound x) (upper-bound y))
(- (upper-bound x) (lower-bound y))))


練習問題 2.9

繰り返しになるけど、区間 $c_x\pm{w_x}$ と $c_y\pm{w_y}$ を、

加算した結果は $(c_x+c_y)\pm(w_x+w_y)$。

減算した結果は $(c_x-c_y)\pm(w_x+w_y)$。

どちらも区間の「幅」は $(w_x+w_y)$ になる。

掛け算と割り算では、こうはならないことを確かめよう。


_.scm

(define (width-interval x)

(- (upper-bound x) (lower-bound x)))

(define a (make-interval 1.0 2.0))
(define b (make-interval 3.0 5.0))

gosh> (width-interval (add-interval a b))
3.0
gosh> (width-interval (sub-interval a b))
3.0
gosh> (width-interval (mul-interval a b))
7.0
gosh> (width-interval (div-interval a b))
0.4666666666666666



練習問題 2.10

割り算を行なう手続き div-interval を見直してみよう。


_.scm

(define (div-interval x y)

(mul-interval
x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y)))))

下限値と上限値の逆数によって区間を作成し、それを掛け算している。

引数yにゼロをまたぐ区間を与えると、この逆数区間は下限値より上限値が小さくなってしまう。例えば -1.0 〜 1.0 という区間を与えると、 1.0 〜 -1.0 という区間が生成されてしまうのだ。

エラー処理を追加しよう。


_.scm

(define (div-interval x y)

(if (< (* (lower-bound y) (upper-bound y)) 0)
(error "ゼロをまたぐ区間で割ることはできません。")
(mul-interval
x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y))))))

実行結果。


_.scm

(define a (make-interval 1.0 2.0))

(define b (make-interval -1.0 1.0))

gosh> (div-interval a b)
*** ERROR: ゼロをまたぐ区間で割ることはできません。



練習問題 2.11

区間の掛け算を行なう mul-interval 手続きは、内部で4回も掛け算を行なう。これを、区間の両端の符号について場合分けすると、掛け算の数を減らせる。

4回も掛け算を行わなければいけないのは、両辺が共にゼロをまたぐ場合だけだ。他は2回ですむ。


_.scm

(define (mul-interval 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)))))))))

実行結果。


_.scm

gosh> (mul-interval (make-interval 1 2) (make-interval 3 4))

(3 . 8)
gosh> (mul-interval (make-interval 1 2) (make-interval -4 -3))
(-8 . -3)
gosh> (mul-interval (make-interval 1 2) (make-interval -3 4))
(-6 . 8)
gosh> (mul-interval (make-interval -2 -1) (make-interval 3 4))
(-8 . -3)
gosh> (mul-interval (make-interval -2 -1) (make-interval -4 -3))
(3 . 8)
gosh> (mul-interval (make-interval -2 -1) (make-interval -3 4))
(-8 . 6)
gosh> (mul-interval (make-interval -1 2) (make-interval 3 4))
(-4 . 8)
gosh> (mul-interval (make-interval -1 2) (make-interval -4 -3))
(-8 . 4)
gosh> (mul-interval (make-interval -1 2) (make-interval -3 4))
(-6 . 8)
gosh> (mul-interval (make-interval -3 4) (make-interval -1 2))
(-6 . 8)

2.12-2.16 はパス。