SICP (16)

Ben の謎めいた発言のおかげ (でもないが) で進捗悪い。ってかわしのアタマが悪いんだろな。(とほほほ

問題 2.7

試験は略で実装を。

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

えーと、div-interval の実装の意味が最初分かってなかった。

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

最初、何故に upper と lower の位置を逆転させるのか、が意味不明だった。mul-interval する時に

• (* (lower-bound x) (lower-bound y))
• (* (lower-bound x) (upper-bound y))
• (* (upper-bound x) (lower-bound y))
• (* (upper-bound x) (upper-bound y))

の一番 {小さい, 大きい} ソレが所定の位置に設定されるんなら make-interval に渡すのはどっちでもいいじゃん、とかワケワカな感想を持っていたりなんかしていたんですが、一応 make-interval の作法に従っているんですね。小さい方が最初で大きい方が次、みたいな。(何故こんな感想を持ったか、というと問題 2.11 が悪い
ってか、分子が同じ値なら分母が大きい方が値としては小さくなる、という常識が (以下[略

問題 2.8

これも試験は略で。

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

引いただけ。(を

ちなみに差の最小値は二つの下限 (lower-bound) の差で、最大値は二つの上限 (upper-bound) の差となる、で良いかな。

問題 2.9

スルーしたいんですが、例示の努力はしてみよう。
節の頭のサンプルの例で

gosh> i1
(6.12 . 7.48)
gosh> i2
(4.465 . 4.935)
gosh> 

という二つの区間を用意して、まず加算。

gosh> (add-interval i1 i2)
(10.585 . 12.415)
gosh> 

ちなみに許容誤差を無視した抵抗値は i1 は 6.8 オームで i2 は 4.7 オーム。この加算と add-intarval な値の平均を比較してみる。

gosh> (+ 6.8 4.7)
11.5
gosh> (/ (+ (lower-bound (add-interval i1 i2)) (upper-bound (add-interval i1 i2))) 2)
11.5
gosh> 

あるいは減算。

gosh> (sub-interval i1 i2)
(1.6550000000000002 . 2.545000000000001)
gosh>

加算と同じ要領にて確認してみる。

gosh> (- 6.8 4.7)
2.0999999999999996
gosh> (/ (+ (lower-bound (sub-interval i1 i2)) (upper-bound (sub-interval i1 i2))) 2)
2.1000000000000005
gosh>

加算も減算もセンターな値からその両翼まできれいに区間の幅を表現している。対して乗算と除算について。まず乗算を。

gosh> (* 6.8 4.7)
31.96
gosh> (mul-interval i1 i2)
(27.3258 . 36.9138)
gosh> (/ (+ (lower-bound (mul-interval i1 i2)) (upper-bound (mul-interval i1 i2))) 2)
32.1198
gosh> 

センターの値が微妙だが、これは誤差の範囲外だな。(って本当か??
除算も試してみます。

gosh> (/ 6.8 4.7)
1.4468085106382977
gosh> (div-interval i1 i2)
(1.2401215805471126 . 1.6752519596864504)
gosh> (/ (+ 1.2401215805471126 1.6752519596864504) 2)
1.4576867701167815
gosh>

むむむ、微妙かも。この問題はもう少し考えさせて下さひ。

問題 2.10

これは 0 divide と勝手読みしてがんがん進める。サンプルの div-interval は以下のように修正を。

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

で、以下を追加。

(define (div-interval x y)
  (cond ((= (lower-bound y) 0) (error "lower-y is zero"))
	((= (upper-bound y) 0) (error "upper-y is zero"))
	(else wrap-div-interval x y)))

終わり方微妙かも。

問題 2.11

これ、苦労しました。mul-interval を要求されたソレで書いたのは test という手続きです。以下。

(define (test x y)
  (cond 
   ;; x は全部正
   ((>= (lower-bound x) 0)
    (cond 
     ;; y は全部正
     ((>= (lower-bound y) 0)
      ;; (* (lower-bound x) (lower-bound y)) が最小
      ;; (* (upper-bound x) (upper-bound y)) が最大
      (make-interval (* (lower-bound x) (lower-bound y))
		     (* (upper-bound x) (upper-bound y)))
      )
     ;; y は全部負
     ((< (upper-bound y) 0)
      ;; (* (upper-bound x) (lower-bound y)) が最小
      ;; (* (lower-bound x) (upper-bound y)) が最大
      (make-interval (* (upper-bound x) (lower-bound y))
		     (* (lower-bound x) (upper-bound y)))
      )
     ;; y は片側のみ負
     (else
      ;; (* (upper-bound x) (lower-bound y)) が最小
      ;; (* (upper-bound x) (upper-bound y)) が最大
      (make-interval (* (upper-bound x) (lower-bound y))
		     (* (upper-bound x) (upper-bound y)))
      ))
    )
   ;; x は全部負
   ((< (upper-bound x) 0)
    (cond 
     ;; y は全部正
     ((>= (lower-bound y) 0)
      ;; (* (lower-bound x) (upper-bound y)) が最小
      ;; (* (upper-bound x) (lower-bound y)) が最大
      (make-interval (* (lower-bound x) (upper-bound y))
		     (* (upper-bound x) (lower-bound y)))
      )
     ;; y は全部負
     ((< (upper-bound y) 0)
      ;; (* (upper-bound x) (upper-bound y)) が最小
      ;; (* (lower-bound x) (lower-bound y)) が最大
      (make-interval (* (upper-bound x) (upper-bound y))
		     (* (lower-bound x) (lower-bound y)))
      )
     ;; y は片側のみ負
     (else
      ;; (* (lower-bound x) (upper-bound y)) が最小
      ;; (* (lower-bound x) (lower-bound y)) が最大
      (make-interval (* (lower-bound x) (upper-bound y))
		     (* (lower-bound x) (lower-bound y)))
      ))
    )
   ;; x は片側のみ負 (ってか、else で OK か)
;   ((and (< (lower-bound x) 0) (>= (upper-bound x) 0))
   (else
    (cond 
     ;; y は全部正
     ((>= (lower-bound y) 0)
      ;; (* (lower-bound x) (upper-bound y)) が最小
      ;; (* (upper-bound x) (upper-bound y)) が最大
      (make-interval (* (lower-bound x) (upper-bound y))
		     (* (upper-bound x) (upper-bound y)))
      )
     ;; y は全部負
     ((< (upper-bound y) 0)
      ;; (* (upper-bound x) (lower-bound y)) が最小
      ;; (* (lower-bound x) (lower-bound y)) が最大
      (make-interval (* (upper-bound x) (lower-bound y))
		     (* (lower-bound x) (lower-bound y)))
      )
     ;; y は片側のみ負
     (else
      ;; (min (* (lower-bound x) (upper-bound y)) 
      ;;      (* (upper-bound x) (lower-bound y))) が最小
      ;; (max (* (upper-bound x) (upper-bound y)) 
      ;;      (* (lower-bound x) (lower-bound y))) が最大
      (make-interval (min (* (lower-bound x) (upper-bound y)) 
			  (* (upper-bound x) (lower-bound y)))
		     (max (* (upper-bound x) (upper-bound y)) 
			  (* (lower-bound x) (lower-bound y))))
      )))))

なんか目がちかちかする。まだリファクタリングできそうだけど、このままで。

確認用の試験は以下です。

(define-test-case "(mul (+ +) (+ +)) test"
  ("mul test (1)"
   (let ((i1 (make-interval 1 2))
	 (i2 (make-interval 3 4)))
     (assert-equal (* (lower-bound i1) (lower-bound i2))
		   (lower-bound (test i1 i2)))
     (assert-equal (* (upper-bound i1) (upper-bound i2))
		   (upper-bound (test i1 i2)))
     )))


(define-test-case "(mul (+ +) (- -)) test"
  ("mul test (2)"
   (let ((i1 (make-interval 1 2))
	 (i2 (make-interval -3 -2)))
     (assert-equal (* (upper-bound i1) (lower-bound i2))
		   (lower-bound (test i1 i2)))
     (assert-equal (* (lower-bound i1) (upper-bound i2))
		   (upper-bound (test i1 i2)))
     )))

(define-test-case "(mul (+ +) (- +)) test"
  ("mul test (3)"
   (let ((i1 (make-interval 1 2))
	 (i2 (make-interval -3 1)))
     (assert-equal (* (upper-bound i1) (lower-bound i2))
		   (lower-bound (test i1 i2)))
     (assert-equal (* (upper-bound i1) (upper-bound i2))
		   (upper-bound (test i1 i2)))
     )))

(define-test-case "(mul (- -) (+ +)) test"
  ("mul test (4)"
   (let ((i1 (make-interval -2 -1))
	 (i2 (make-interval 1 2)))
     (assert-equal (* (lower-bound i1) (upper-bound i2))
		   (lower-bound (test i1 i2)))
     (assert-equal (* (upper-bound i1) (lower-bound i2))
		   (upper-bound (test i1 i2)))
     )))

(define-test-case "(mul (- -) (- -)) test"
  ("mul test (5)"
   (let ((i1 (make-interval -2 -1))
	 (i2 (make-interval -3 -2)))
     (assert-equal (* (upper-bound i1) (upper-bound i2))
		   (lower-bound (test i1 i2)))
     (assert-equal (* (lower-bound i1) (lower-bound i2))
		   (upper-bound (test i1 i2)))
     )))

(define-test-case "(mul (- -) (- +)) test"
  ("mul test (6)"
   (let ((i1 (make-interval -2 -1))
	 (i2 (make-interval -1 2)))
     (assert-equal (* (lower-bound i1) (upper-bound i2))
		   (lower-bound (test i1 i2)))
     (assert-equal (* (lower-bound i1) (lower-bound i2))
		   (upper-bound (test i1 i2)))
     )))

(define-test-case "(mul (- +) (+ +)) test"
  ("mul test (7)"
   (let ((i1 (make-interval -2 1))
	 (i2 (make-interval 1 2)))
     (assert-equal (* (lower-bound i1) (upper-bound i2))
		   (lower-bound (test i1 i2)))
     (assert-equal (* (upper-bound i1) (upper-bound i2))
		   (upper-bound (test i1 i2)))
     )))

(define-test-case "(mul (- +) (- -)) test"
  ("mul test (8)"
   (let ((i1 (make-interval -2 1))
	 (i2 (make-interval -4 -3)))
     (assert-equal (* (upper-bound i1) (lower-bound i2))
		   (lower-bound (test i1 i2)))
     (assert-equal (* (lower-bound i1) (lower-bound i2))
		   (upper-bound (test i1 i2)))
     )))

(define-test-case "(mul (- +) (- +)) test"
  ("mul test (9)"
   (let ((i1 (make-interval -3 1))
	 (i2 (make-interval -2 2)))
     (assert-equal (min (* (lower-bound i1) (upper-bound i2))
			(* (upper-bound i1) (lower-bound i2)))
		   (lower-bound (test i1 i2)))
     (assert-equal (max (* (upper-bound i1) (upper-bound i2))
			(* (lower-bound i1) (lower-bound i2)))
		   (upper-bound (test i1 i2)))
     )))

(define-test-case "(mul (- +) (- +)) test"
  ("mul test (10)"
   (let ((i1 (make-interval -1 3))
	 (i2 (make-interval -2 4)))
     (assert-equal (min (* (lower-bound i1) (upper-bound i2))
			(* (upper-bound i1) (lower-bound i2)))
		   (lower-bound (test i1 i2)))
     (assert-equal (max (* (upper-bound i1) (upper-bound i2))
			(* (lower-bound i1) (lower-bound i2)))
		   (upper-bound (test i1 i2)))
     )))

2.11 はまだ残りがあるな。
なるべく抽象的に検討を進めるべき、というソレに気づけば話は早いんですが、なかなかそれに気がつかない。

続きは別途。