Studio H.F.F.

1.1.7 例:Newton法による平方根

Newton法という方法で平方根を求めるプログラムの例が載っていました。再帰が自然に出てきたあたりがLispっぽい。Gaucheでプログラムを実行させようとしたところ、squareがないとエラーが出ました。標準ライブラリの差かな？幸い(* guess guess)に簡単に置き換えられるので、こちらで対応。

問題 1.6

先日、自分が述べた疑問への解答がさっそく登場。

condだけじゃなくて、ifが用意されているのが、Lispらしくないと思った。cond/elseで書けるわけだから、シンタックスシュガーなわけで。シンプルを良しとするLispらしくない印象。

condを元にifを自作した場合、通常の関数と同様に処理される。つまり、「作用法的順序の評価」が行われる。ifの引数となるpredicate・then-clause・else-clauseが評価された後、それぞれの値がifに渡される。predicateの内容によって、then-clause、もしくはelse-clauseが実行されるのではなくなってしまう。このため、前述の「Newton法による平方根」のように再帰中にifを使用した場合、永遠に終了出来ないようになってしまう。このため、ifは専用の構文として、通常の関数とは違うルールで処理する必要がある。

実際に無限ループになることを確認。

問題 1.7

非常に小さな数の場合、有効な平方根を求める前に処理が終了してしまう。

gosh> (sqrt 0.0000000000000000001)
0.03125
gosh> (* 0.03125 0.03125)
9.765625e-4

非常に大きな数の場合、平方根を求めるのに時間がかかってしまう。

再帰の前回と今回の変化量に着目して充分に小さくなったかで判定するバージョン。

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

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

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

(define (good-enough? guess variation)
  (< (abs (* variation 1000)) guess))

(define (sqrt x)
  (sqrt-iter 1.0 1.0 x))

非常に小さな数。

gosh> (sqrt 1e-20)
1.000000000002308e-10

非常に大きな数。

gosh> (sqrt 1e20)
1.0000000000023079e10

演算時間も問題なし。