開発環境
- 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.
$
0 コメント:
コメントを投稿