ニュートン法で平方根を求めるという問題。一般的に、数学の方法で問題の解き方を記述するとdeclarative (what is) descriptionになる。けれども、コンピュータでプログラミングをする時にはimperative (how to) descriptionで考えないとprocedureは書けない、といった内容だった。
ニュートン法で平方根を求めるプログラムの作成は、非常に分かりやすく書かれていたので、割愛。さり気なく繰り返しの為の再帰呼び出しが入っていて、かつそれが末尾再帰になっているというのがさすが。
Exercise 1.6
new-if procedureに(good-enough? guess x)とguessと(sqrt-iter (improve guess x) x)))が渡されて、それぞれがcondのpredicate, then-clause, else-clauseに展開されて評価される、で良いと思うんだけど。何か実行に問題があったりするんだろうか。
何が問題なのか分からなかったので解答を見てみて、納得。そうか、普通のprocedureだと、全てのoperandが評価されてしまうんだ。そうなると、else-clauseにある再帰がthen-clauseと一緒に必ず評価されてしまうから、無限再帰に陥ると。
この辺りはまだよく分かっていない気がする。applicative-order evaluation辺りも要復習。
Exercise 1.7
小さい数の平方根を求める時は、good-enough?で指定した精度よりも小さな数の平方根を求められない。
大きい数の平方根を求める時は、squareで自乗を求める時にprecisionの限界を超える恐れがある。例えば10^10までしか扱えないようなシステムで10^6の平方根を求めようとする。まず(sqrt-iter 1.0 10^6)が評価され、その中で(sqrt-iter 5*10^5+0.5 10^6)が評価され、その中で(square 5*10^5+0.5)が評価される。この評価値は約25*10^10なので、precisionの限界を超える。
これらを考慮して改良したコードは以下の通り。
(define (square-root x)
(square-root-iter 1.0 x))
(define (square-root-iter y x)
(if (good-enough? y (improve x y))
(improve x y)
(square-root-iter (improve x y) x)))
(define (good-enough? x y)
(< (abs (- x y)) 0.001))
(define (improve x y)
(/ (+ y (/ x y)) 2.0))この問題はよく分からなかった。あまり自信が無い。
プログラムも効率が悪い。(improve x y)の結果を変数に代入できればいいんだけど。解答は見てないけど、多分もっと効率のいい実装方法があるんだろう。まだSchemeに慣れていないので、Rubyでプログラムを作ってみて、その後Schemeに変換しているのもよくない。早く慣れないと。
Exercise 1.8
(define (cbrt-iter guess x)
(if (good-enough? guess x)
guess
(cbrt-iter (improve guess x)
x)))
(define (good-enough? guess x)
(< (abs (- (cublic guess) x)) 0.001))
(define (improve guess x)
(/ (+ (/ x (* guess guess)) (* 2 guess)) 3))
(define (cublic x) (* x x x))
(define (cbrt x)
(cbrt-iter 1.0 x))cbrt-iterとgood-enough?は本質的に何も変わっていない。improve中の数式は、SICPに書いてあった通り。
