Scheme - プログラムの要素(例: Newton 法による平方根)

計算機プログラムの構造と解釈
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(原著)、和田英一(翻訳)、ピアソンエデュケーション)の1(手続きによる抽象の構築)、1.1(プログラムの要素)、1.1.7(例: Newton 法による平方根)の問題を解いてみる。

問題 1.6.

順に評価していく。

(sqrt 2)

(sqrt-iter 1.0 2)

(new-if (good-enough? 1.0 2)
        1.0
        (sqrt-iter (improve 1.0 2)
        2))

ここで、演算子(new-if)の非演算子((good-enough? 1.0 2)、(1.0)、(sqrt-iter (improve 1.0 2) 2.0))を左から順に評価していく。

(good-enough? 1.0 2)

(< (abs (- (square 1.0) 2)) 0.001)

(< (abs (- 1.0 2)) 0.001)

(< (abs  1.0) 0.001)

(< 1.0 0.001)

#f

次の非演算子を評価。

1.0

さらに次の非演算子を評価。

(sqrt-iter (improve 1.0 2) 2)

(sqrt-iter (average 1.0 (/ 2 1.0)) 2)

(sqrt-iter (average 1.0 2.0) 2)

(sqrt-iter 1.5 2.0)

(new-if (good-enough? 1.5 2.0)
        1.5
        (sqrt-iter (improve 1.5 2)
                   2))

(new-if #f 1.5 (sqrt-iter 1.75 2))

ここで、ifの場合は、(good-enough? guess x)が#tになった場合、この評価は行われないけど、new-ifの場合は、(good-enough? guess x)が#tか#fかに関わらず評価される(作用的順序の評価だから)ので、無限に評価されることになる。

問題 1.7

非常に小さい数の場合、すぐに(good-enough? guess x)が#tに評価されてしまい、計算速度は速いけど誤差が大きくなってしまう。

逆に、非常に大きい数の場合、(good-enough? guess x)がなかなか#tに評価されず、計算に時間がかかり、そしてかかる時間に比べて誤差が少なくなる速度が落ちていき、効率が良くない。

確認。

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

$ scheme
MIT/GNU Scheme running under MacOSX
Type `^C' (control-C) followed by `H' to obtain information about interrupts.

Copyright (C) 2011 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Image saved on Friday April 13, 2012 at 9:02:52 AM
  Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118
  Edwin 3.116

1 ]=> (define (square x) (* x x))

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (sqrt x)
  (sqrt-iter 1.0 x))
;Value: square

1 ]=> 
;Value: sqrt-iter

1 ]=> 
;Value: improve

1 ]=> 
;Value: average

1 ]=> 
;Value: good-enough?

1 ]=> 

;Value: sqrt

1 ]=> (sqrt 0.00000000000000000000000000000000000000000000000001)

;Value: .03125

1 ]=> (* .03125 0.3125)

;Value: .009765625

1 ]=> (sqrt 100000000000000000000000000000000000000000000000000)
^C
Interrupt option (? for help): 
;Quit!

1 ]=> ^D
End of input stream reached.
Moriturus te saluto.
$

(非常に大きい数の倍は評価がなかなか終わらなかったのでctr+cで中断。)

新たな戦略による設計。

予想値の変化率が(0.99から1.001)の間になったら近似を終了することに。(0.99は非常に小さい数、1.001は非常に大きい数の場合)

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

$ scheme
MIT/GNU Scheme running under MacOSX
Type `^C' (control-C) followed by `H' to obtain information about interrupts.

Copyright (C) 2011 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Image saved on Friday April 13, 2012 at 9:02:52 AM
  Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118
  Edwin 3.116

1 ]=> (define (square x) (* x x))

(define (sqrt-iter guess old-guess x)
  (if (good-enough? guess old-guess)
      guess
      (sqrt-iter (improve guess x)
                 guess x)))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

(define (good-enough? guess old-guess)
  (< (abs (- 1
             (/ guess old-guess)))
     0.001))

(define (sqrt x)
  (sqrt-iter 1.0 0.1 x))
;Value: square

1 ]=> 
;Value: sqrt-iter

1 ]=> 
;Value: improve

1 ]=> 
;Value: average

1 ]=> 
;Value: good-enough?

1 ]=> 

;Value: sqrt

1 ]=> (sqrt 4)

;Value: 2.0000000929222947

1 ]=> (sqrt 0.00000000000000000000000000000000000000000000000001)

;Value: 1.0000003807575104e-25

1 ]=> (sqrt 100000000000000000000000000000000000000000000000000)

;Value: 1.0000003807575104e25

1 ]=> (sqrt 1.e-100)

;Value: 1.0000000000002005e-50

1 ]=> (sqrt 1.e100)

;Value: 1.0000000000002003e50

1 ]=> ^D
End of input stream reached.
Moriturus te saluto.
$

問題 1.8

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

$ scheme
MIT/GNU Scheme running under MacOSX
Type `^C' (control-C) followed by `H' to obtain information about interrupts.

Copyright (C) 2011 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Image saved on Friday April 13, 2012 at 9:02:52 AM
  Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118
  Edwin 3.116

1 ]=> (define (square x) (* x x))

(define (cubic-root-iter guess old-guess x)
  (if (good-enough? guess old-guess)
      guess
      (cubic-root-iter (improve guess x)
                 guess x)))

(define (improve guess x)
  (/ (+ (/ x (square guess))
        (* 2 guess))
     3))

(define (good-enough? guess old-guess)
  (< (abs (- 1
             (/ guess old-guess)))
     0.001))

(define (cubic-root x)
  (cubic-root-iter 1.0 0.1 x))
;Value: square

1 ]=> 
;Value: cubic-root-iter

1 ]=> 
;Value: improve

1 ]=> 
;Value: good-enough?

1 ]=> 

;Value: cubic-root

1 ]=> (cubic-root 1)

;Value: 1.

1 ]=> (cubic-root 8)

;Value: 2.000000000012062

1 ]=> (cubic-root 27)

;Value: 3.0000005410641766

1 ]=> (cubic-root 64)

;Value: 4.000000000076121

1 ]=> (cubic-root 125)

;Value: 5.000000000287929

1 ]=> (cubic-root 1000000000000000000000000000000)

;Value: 10000001763.831392

1 ]=> (cubic-root 0.000000000000000000000000000001)

;Value: 1.0000000733193899e-10

1 ]=> (cubic-root 1.e99)

;Value: 1.0000000000029435e33

1 ]=> (cubic-root 1.e-99)

;Value: 1.0000000004754588e-33

1 ]=> ^D
End of input stream reached.
Moriturus te saluto.
$

Kamimura's blog

2013年4月21日日曜日

Scheme - プログラムの要素(例: Newton 法による平方根)

0 コメント:

コメントを投稿