SICP: Exercise 1.7

good-enough? の問題点

二乗値の誤差がある閾値（0.001）未満になっていることで「十分良い」と判断する good-enough? は、とても小さな数の平方根を探すのにはそれほど効果的ではない。また、現実のコンピュータでは数値演算はほとんど常に限られた精度で行われるので、とても大きな数の平方根を探すのにも適していない。

例えば、小さい数では

(square (sqrt-iter 1 1e-9))
; 9.765631660156936e-4

となって、正しい平方根が求められていないことが分かる。これは、冒頭に書いたとおり二乗値の誤差が 0.001 未満ならばパスするようになっているため。二乗値がそれより小さい場合は当然ずれが大きくなってしまう。

また、大きい数では

(sqrt-iter 1 1e13)

などとすると、いつまでたっても計算が終わらない。これは、ニュートン法の平均をとる過程で、小さい guess と非常に大きい guess / x を足した際に情報落ちが生じてしまい、guess が正しい値に近づかなくなってしまうため。

good-enough? 実装の別の戦略

good-enough? 実装の別の戦略は、一回のイテレーションでどれだけ guess が変化するか調べ、変化が十分に小さいときに止める、というもの。例えば

(define (average x y)
  (/ (+ x y) 2))
 
(define (improve guess x)
  (average guess (/ x guess)))
 
(define (good-enough?-change before after)
  (< (abs (- after before)) 1e-8))
 
(define (sqrt-iter-change guess x)
  (if (good-enough?-change guess (improve guess x))
    guess
    (sqrt-iter-change (improve guess x) x)))

などとすれば、二乗値の大小にかかわらずうまく計算できた。

(square (sqrt-iter-change 1 1e-9))
; 1.0000002521736707e-9
(square (sqrt-iter-change 1 1e13))
; 1.0000000000000002e13

追記

上の good-enough?-change では前後の差の大きさを閾値で判別していたが、相対値で判別する方が良かった。上のだと二乗値が 1e-16 以下のときおかしくなる。

(define (good-enough?-change before after)
  (< (abs (- after before)) (* before 0.001)))