Scheme - データによる抽象の構築(区間得算術演算子(代数的に等価な異なる式と誤差))

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション)の2(データによる抽象の構築)、2.1(データ抽象入門)、2.1.4(拡張問題: 区間算術演算)の問題 2.14、問題 2.15、問題 2.16を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 2.14

コード

sample.scm

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

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

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

(define (width i)
  (/ (- (upper-bound i) (lower-bound i)) 2))

(define (percent i)
  (let ((c (center i))
        (w (width i)))
    (* (/ w c) 100)))

(define (center i)
  (/ (+ (lower-bound i) (upper-bound i)) 2))

(define (make-center-percent c p)
  (let ((w (* c (/ p 100))))
    (make-interval (- c w) (+ c w))))

(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 ((x1 (lower-bound x))
        (y1 (upper-bound x))
        (x2 (lower-bound y))
        (y2 (upper-bound y))
        (negative? (lambda (n) (< n 0))))
    (let ((x1-sign (negative? x1))
          (y1-sign (negative? y1))
          (x2-sign (negative? x2))
          (y2-sign (negative? y2)))
      (cond ((and x1-sign (not y1-sign) x2-sign (not y2-sign))
             (let ((p1 (* x1 y2))
                   (p2 (* x2 y1))
                   (p3 (* x1 y1))
                   (p4 (* y2 y2)))
                   (make-interval (min p1 p2) (max p3 p4))))
            ((and (not x1-sign) (not x2-sign))
             (make-interval (* x1 x2) (* y1 y2)))
            ((and (not x1-sign) (not y2-sign))
             (make-interval (* y1 x2) (* y1 y2)))
            ((not x1-sign) (make-interval (* y1 x2) (* x1 y2)))
            ((and x1-sign (not y1-sign) (not x2-sign))
             (make-interval (* x1 y2) (* y1 y2)))
            ((and x1-sign (not y1-sign))
             (make-interval (* y1 x2) (* x1 x2)))
            (y2-sign (make-interval (* y1 y2) (* x1 x2)))
            ((not x2-sign) (make-interval (* x1 y2) (* y1 x2)))
            (else (make-interval (* x1 y2) (* x1 x2)))))))

(define (div-interval x y)
  (cond ((= (width y) 0) (newline) (display "error"))
        (else (mul-interval x
                            (make-interval (/ 1.0 (upper-bound y))
                                           (/ 1.0 (lower-bound y)))))))

(define (par1 r1 r2)
  (div-interval (mul-interval r1 r2)
                (add-interval r1 r2)))

(define (par2 r1 r2)
  (let ((one (make-interval 1 1)))
    (div-interval one
                  (add-interval (div-interval one r1)
                                (div-interval one r2)))))

(define (print-interval i)
  (let ((c (center i))
        (p (percent i)))
    (newline)
    (display c)
    (display " ± ")
    (display (* c (/ p 100.0)))))


(define a (make-center-percent 100 5))

(define b (make-center-percent 200 5))

(define aa (div-interval a a))

(define ab (div-interval a b))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

1 ]=> (print-interval (par1 a b))

67.33500417710944 ± 10.033416875522137
;Unspecified return value

1 ]=> (print-interval (par2 a b))

66.66666666666666 ± 3.3333333333333357
;Unspecified return value

1 ]=> (print-interval aa)

1.0050125313283207 ± .10025062656641592
;Unspecified return value

1 ]=> (print-interval ab)

.5025062656641603 ± .05012531328320796
;Unspecified return value

1 ]=> (print-interval (div-interval (add-interval a b) (add-interval a b))) 

1.005012531328321 ± .1002506265664161
;Unspecified return value

確かに、par1とpar2で異なる結果になっているのでLemの文句は正しい。

また、ある区間を同じ区間で割ったらもとの区間と異なる結果になる。(aaより)

問題 2.15

正しい。前問、問題 2.14で分かったように、不確かな数を表現する変数が繰り返し現れるたびに誤差が大きくなる。なので、不確かな変数の個数が少ないpar2の方が並列抵抗の「よい」プログラムである。

問題 2.16

非常に難しい問題ということなので、とりあえず次に進むことに。