問題 2.11
mul-interval 手続きに渡される r1, r2 の符号の組み合わせを考えます。
;; r1 r2 ;; + + + + : o ;; + + + - : x ;; + + - + : o ;; + + - - : o ;; + - + + : x ;; + - + - : x ;; + - - + : x ;; + - - - : x ;; - + + + : o ;; - + + - : x ;; - + - + : o ;; - + - - : o ;; - - + + : o ;; - - + - : x ;; - - - + : o ;; - - - - : o
全部で 16 通りになりますが、
下限許容限界値がプラスで上限許容限界値がマイナスというパターンはありえません。
よって Ben の言う通り 9 通りとなります。(〇がついている行)
次に 9 通りについて、p1, p2, p3, p4 の符号と、どれが最小値、最大値となるかを考えます。
;; x y p1 2 3 4 ;; + + + + : + + + + p1 p4 ;; + + - + : - + - + p3 p4 ;; + + - - : - - - - p4 p1 ;; - + + + : - - + + p2 p4 ;; - + - + : + - - + (p2 p3) p4 ;; - + - - : + + - - p4 p2 ;; - - + + : - - - - p4 p1 ;; - - - + : + - + - p4 p3 ;; - - - - : + + + + p1 p4
真ん中付近にあるとおり、p2 と p3 が両方マイナスになり、
どちらが小さいか決められないケースが 1 つだけあることがわかります。
これが Ben が言っていた、
「3 回以上のかけ算が必要になるのはその中のひとつだけだよ。」
に該当します。
(define (p x)
(>= x 0))
(define (m x)
(< x 0))
;; p1 (* lx ly)
;; p2 (* lx uy)
;; p3 (* ux ly)
;; p4 (* ux uy)
(define (mul-interval x y)
(let ((lx (lower-bound x))
(ux (upper-bound x))
(ly (lower-bound y))
(uy (upper-bound y)))
(cond ((and (p lx) (p ux) (p ly) (p uy))
(make-interval (* lx ly) (* ux uy)))
((and (p lx) (p ux) (m ly) (p uy))
(make-interval (* ux ly) (* ux uy)))
((and (p lx) (p ux) (m ly) (m uy))
(make-interval (* ux uy) (* lx ly)))
((and (m lx) (p ux) (p ly) (p uy))
(make-interval (* lx uy) (* ux uy)))
((and (m lx) (p ux) (m ly) (p uy))
(make-interval (min (* lx uy) (* ux ly)) (* ux uy)))
((and (m lx) (p ux) (m ly) (m uy))
(make-interval (* ux uy) (* lx uy)))
((and (m lx) (m ux) (p ly) (p uy))
(make-interval (* ux uy) (* lx ly)))
((and (m lx) (m ux) (m ly) (p uy))
(make-interval (* ux uy) (* ux ly)))
((and (m lx) (m ux) (m ly) (m uy))
(make-interval (* lx ly) (* ux uy)))
(else (error "impossible case -- MUL-INTERVAL")))))Ben の言うとおりに修正しましたが・・・
Ben ちゃん、こんなんで良いかな？ｗｗｗ
プログラムがすっごく読みにくいんだけど大丈夫かな？ｗｗｗｗｗｗｗ
Ben はうなづいているので良しとしますｗｗｗ (本当か？)
必要な掛け算のパターンについて研究するのは別に良いとは思いますが、
ここまで読みにくいプログラムにしてまで掛け算の回数を減らす実装をする意義があるのか？
については疑問を抱かざるを得ません。
