SICP問題1.7

元々のここまでで使用している平方根を求める手続き

(define (square x) (* x x))
(define (sqrt x)
  (sqrt-iter 1.0 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))

• 小さい値の場合

小さい値の場合、予測値guessの自乗値が許容値(0.001)より小さくなってしまうため、十分な改善(improve)が行われない、と予想される。で実験。

(sqrt 0.01)
; => 0.10032578510960605
(square 0.10032578510960605)
; => 0.01006526315785885
(sqrt 0.001)
; => 0.04124542607499115
(square 0.04124542607499115)
; => 0.0017011851721075596
(sqrt 0.0001)
; => 0.03230844833048122
(square 0.03230844833048122)
; => 0.0010438358335233748

• 大きい値の場合

次は大きい値の場合。有効桁数の精度を超えるので値の改善がなされないと予想。で実験。

(sqrt 10000)
; => 100.00000025490743
(sqrt 1000000)
; => 1000.0000000000118
(sqrt 1000000000)
; => 31622.776601684047
(square 31622.776601684047)
; => 1.0000000000000161e9
(sqrt 1000000000000)
; => 1000000.0
(square 1000000.0)
; => 1.0e12
(sqrt 2000000000000)
; => 1414213.5623730952
(square 1414213.5623730952)
; => 2.0000000000000005e12
(sqrt 1000000000000000)
; => 返って来ない!!

んーと、そういうことではナサゲですね。
どうやら、大きい数になると浮動小数点数の分解能が許容値(0.001)をこえてしまうため、improveで値の改善はなされるけど判定基準を満たせずに無限ループに陥るということのようです。

ということで((新しいguess - 前のguess)/前のguess)を変化の大きさとし、閾値以下なら十分改善したと見なすコードに変更してみました。
なお変化の大きさを(新しいguess/前のguess)とかでやると、やっぱり小さい値や大きい値で無限ループに陥るのでダメです。

(define (square x) (* x x))
(define (sqrt x)
  (sqrt-iter 1.0 x x))
(define (sqrt-iter guess last-guess x)
  (if (good-enough? guess last-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 last-guess)
  (< (abs (/ (- guess last-guess) last-guess)) 0.001))

で実験。

(sqrt 0.0001)
; => 0.010000000025490743
(sqrt 0.001)
; => 0.03162278245070105
(sqrt 1000000000000)
; => 1000000.103461242

OKそうです。