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

[hiroshi-manabe様の日本語訳](https://github.com/hiroshi-manabe/sicp-pdf)を使わせてもらいます。
練習問題等は[Gauche](http://practical-scheme.net/gauche/index-j.html)で実行。

[前回はこちら](https://qiita.com/shuetsu@github/items/32636d057c3788b4680e)

## 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 はパス。