問題1.7

小さい数について。

CL-USER> (mysqrt 0.0001)
0.032308448
CL-USER> (* (mysqrt 0.0001) (mysqrt 0.0001))
0.0010438358

となり、good-enough?での許容値より小さい数には上手く動作しない。

大きい数について。

CL-USER> (mysqrt 1.0e20)

; デバッガへ
FLOATING-POINT-OVERFLOW detected
   [Condition of type FLOATING-POINT-OVERFLOW]

CL-USER> (trace good-enough?)
NIL
CL-USER> (mysqrt 1.0d29)
0> Calling (GOOD-ENOUGH? 1.0 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 5.0D+28 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 2.5D+28 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.25D+28 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 6.25D+27 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.125D+27 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.5625D+27 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 7.8125D+26 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.90625D+26 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.953125D+26 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 9.765625D+25 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 4.8828125D+25 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 2.44140625D+25 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.220703125D+25 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 6.103515625D+24 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.0517578125D+24 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.52587890625D+24 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 7.62939453125D+23 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.814697265625D+23 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.9073486328125D+23 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 9.5367431640625D+22 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 4.76837158203125D+22 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 2.384185791015625D+22 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.1920928955078126D+22 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 5.960464477539067D+21 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 2.980232238769542D+21 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.4901161193847878D+21 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 7.450580596924274D+20 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.725290298462808D+20 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.8626451492327463D+20 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 9.313225746190575D+19 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 4.656612873148975D+19 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 2.3283064366818615D+19 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.1641532185556791D+19 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 5.820766097073363D+18 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 2.910383057126616D+18 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.4551915457431772D+18 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 7.275958072313265D+17 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.637979723351356D+17 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.8189912360648666D+17 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 9.094983668087334D+16 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 4.547546809403519D+16 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 2.2738833540922676D+16 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.137161565194354D+16 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 5.690204738559249D+15 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 2.8538893993246385D+15 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.444464649808892D+15 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 7.568472253152072D+14 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 4.444871434833608D+14 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.347327645857288D+14 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.167392710266006D+14 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.162281790337874D+14 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.162277660171076D+14 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.162277660168379D+14 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.162277660168379D+14 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.162277660168379D+14 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
; 以下無限ループ

桁溢れを起こしたり、精度の問題で処理が終わらなかったりする。

もうひとつの戦略を実装するコードは、

(defun sqrt-iter (guess prev-guess x)
  (if (good-enough? guess prev-guess)
      guess
      (sqrt-iter (improve guess x) guess x)))

(defun improve (guess x)
  (average guess (/ x guess)))

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

(defun good-enough? (guess prev-guess)
  (< (abs (- 1.0 (/ guess prev-guess))) 0.001))

(defun mysqrt (x)
  (sqrt-iter 1.0 x x))

結果は、

CL-USER> (mysqrt 0.0001)
0.01
CL-USER> (mysqrt 1.0d29)
3.162277660171076D+14

小さな数でも大きな数でも正常に動作する。good-enough?のアルゴリズムの変更によって、桁溢れも起こらない。