暇シリーズ ～Newton法による平方根～

問題 1.7
平方根の計算で使った good-enough? テストは、非常に小さい数の平方根をとる時には効果的ではない。また、実際の計算機では、算術演算は殆んどの場合、限られた精度で実行される。それでわれわれのテストは非常に大きい数にも不適切である。小さい数、大きい数の場合、どのようにテストが失敗するかの例を使ってこのことを説明せよ.

(define (good-enough? guess x)
  (print ";; val=" (abs (- (square guess) x)) " guess=" guess " x=" x)
  (< (abs (- (square guess) x)) 0.001))

まず good-enough? 手続きにデバッグ出力文を仕込んで、値の変化を見てみます。
まず大きい値の場合から。

gosh> (sqrt 100000000000000000000000000000000000000000000000000)
;; val=1.0e50 guess=1.0 x=100000000000000000000000000000000000000000000000000
;; val=2.5000000000000005e99 guess=5.0e49 x=100000000000000000000000000000000000000000000000000
;; val=6.250000000000001e98 guess=2.5e49 x=100000000000000000000000000000000000000000000000000
;; val=1.5625000000000003e98 guess=1.25e49 x=100000000000000000000000000000000000000000000000000
;; val=3.906250000000001e97 guess=6.25e48 x=100000000000000000000000000000000000000000000000000
;; val=9.765625000000002e96 guess=3.125e48 x=100000000000000000000000000000000000000000000000000
;; val=2.4414062500000005e96 guess=1.5625e48 x=100000000000000000000000000000000000000000000000000
;; val=6.103515625000001e95 guess=7.8125e47 x=100000000000000000000000000000000000000000000000000
;; val=1.5258789062500003e95 guess=3.90625e47 x=100000000000000000000000000000000000000000000000000
;; val=3.814697265625001e94 guess=1.953125e47 x=100000000000000000000000000000000000000000000000000
;; val=9.536743164062502e93 guess=9.765625e46 x=100000000000000000000000000000000000000000000000000
;; val=2.3841857910156255e93 guess=4.8828125e46 x=100000000000000000000000000000000000000000000000000
;; val=5.960464477539064e92 guess=2.44140625e46 x=100000000000000000000000000000000000000000000000000
;; val=1.490116119384766e92 guess=1.220703125e46 x=100000000000000000000000000000000000000000000000000
;; val=3.725290298461915e91 guess=6.103515625e45 x=100000000000000000000000000000000000000000000000000
;; val=9.313225746154787e90 guess=3.0517578125e45 x=100000000000000000000000000000000000000000000000000
;; val=2.328306436538697e90 guess=1.52587890625e45 x=100000000000000000000000000000000000000000000000000
;; val=5.820766091346742e89 guess=7.62939453125e44 x=100000000000000000000000000000000000000000000000000
;; val=1.4551915228366855e89 guess=3.814697265625e44 x=100000000000000000000000000000000000000000000000000
;; val=3.637978807091714e88 guess=1.9073486328125e44 x=100000000000000000000000000000000000000000000000000
;; val=9.094947017729284e87 guess=9.5367431640625e43 x=100000000000000000000000000000000000000000000000000
;; val=2.273736754432321e87 guess=4.76837158203125e43 x=100000000000000000000000000000000000000000000000000
;; val=5.684341886080803e86 guess=2.384185791015625e43 x=100000000000000000000000000000000000000000000000000
;; val=1.4210854715202007e86 guess=1.1920928955078126e43 x=100000000000000000000000000000000000000000000000000
;; val=3.552713678800502e85 guess=5.960464477539063e42 x=100000000000000000000000000000000000000000000000000
;; val=8.881784197001254e84 guess=2.9802322387695315e42 x=100000000000000000000000000000000000000000000000000
;; val=2.2204460492503135e84 guess=1.4901161193847657e42 x=100000000000000000000000000000000000000000000000000
;; val=5.551115123125784e83 guess=7.450580596923829e41 x=100000000000000000000000000000000000000000000000000
;; val=1.387778780781446e83 guess=3.725290298461914e41 x=100000000000000000000000000000000000000000000000000
;; val=3.469446951953615e82 guess=1.862645149230957e41 x=100000000000000000000000000000000000000000000000000
;; val=8.673617379884037e81 guess=9.313225746154786e40 x=100000000000000000000000000000000000000000000000000
;; val=2.1684043449710093e81 guess=4.656612873077393e40 x=100000000000000000000000000000000000000000000000000
;; val=5.421010862427523e80 guess=2.3283064365386965e40 x=100000000000000000000000000000000000000000000000000
;; val=1.3552527156068808e80 guess=1.1641532182693482e40 x=100000000000000000000000000000000000000000000000000
;; val=3.388131789017202e79 guess=5.820766091346741e39 x=100000000000000000000000000000000000000000000000000
;; val=8.470329472543005e78 guess=2.9103830456733706e39 x=100000000000000000000000000000000000000000000000000
;; val=2.1175823681357513e78 guess=1.4551915228366853e39 x=100000000000000000000000000000000000000000000000000
;; val=5.293955920339378e77 guess=7.275957614183426e38 x=100000000000000000000000000000000000000000000000000
;; val=1.3234889800848446e77 guess=3.637978807091713e38 x=100000000000000000000000000000000000000000000000000
;; val=3.3087224502121114e76 guess=1.8189894035458566e38 x=100000000000000000000000000000000000000000000000000
;; val=8.271806125530278e75 guess=9.094947017729283e37 x=100000000000000000000000000000000000000000000000000
;; val=2.0679515313825696e75 guess=4.547473508864642e37 x=100000000000000000000000000000000000000000000000000
;; val=5.169878828456424e74 guess=2.273736754432321e37 x=100000000000000000000000000000000000000000000000000
;; val=1.292469707114106e74 guess=1.1368683772161604e37 x=100000000000000000000000000000000000000000000000000
;; val=3.231174267785265e73 guess=5.684341886080802e36 x=100000000000000000000000000000000000000000000000000
;; val=8.077935669463163e72 guess=2.842170943040401e36 x=100000000000000000000000000000000000000000000000000
;; val=2.0194839173657906e72 guess=1.4210854715202005e36 x=100000000000000000000000000000000000000000000000000
;; val=5.048709793414477e71 guess=7.105427357601002e35 x=100000000000000000000000000000000000000000000000000
;; val=1.2621774483536192e71 guess=3.552713678800501e35 x=100000000000000000000000000000000000000000000000000
;; val=3.155443620884048e70 guess=1.7763568394002506e35 x=100000000000000000000000000000000000000000000000000
;; val=7.88860905221012e69 guess=8.881784197001253e34 x=100000000000000000000000000000000000000000000000000
;; val=1.97215226305253e69 guess=4.4408920985006265e34 x=100000000000000000000000000000000000000000000000000
;; val=4.930380657631325e68 guess=2.2204460492503133e34 x=100000000000000000000000000000000000000000000000000
;; val=1.2325951644078312e68 guess=1.1102230246251566e34 x=100000000000000000000000000000000000000000000000000
;; val=3.081487911019578e67 guess=5.551115123125783e33 x=100000000000000000000000000000000000000000000000000
;; val=7.703719777548945e66 guess=2.7755575615628916e33 x=100000000000000000000000000000000000000000000000000
;; val=1.9259299443872363e66 guess=1.3877787807814458e33 x=100000000000000000000000000000000000000000000000000
;; val=4.81482486096809e65 guess=6.938893903907229e32 x=100000000000000000000000000000000000000000000000000
;; val=1.2037062152420222e65 guess=3.469446951953615e32 x=100000000000000000000000000000000000000000000000000
;; val=3.0092655381050526e64 guess=1.734723475976809e32 x=100000000000000000000000000000000000000000000000000
;; val=7.523163845262608e63 guess=8.673617379884074e31 x=100000000000000000000000000000000000000000000000000
;; val=1.8807909613156264e63 guess=4.336808689942095e31 x=100000000000000000000000000000000000000000000000000
;; val=4.701977403288817e62 guess=2.1684043449711626e31 x=100000000000000000000000000000000000000000000000000
;; val=1.1754943508219541e62 guess=1.0842021724858119e31 x=100000000000000000000000000000000000000000000000000
;; val=2.9387358770523853e61 guess=5.421010862433671e30 x=100000000000000000000000000000000000000000000000000
;; val=7.346839692605964e60 guess=2.710505431226059e30 x=100000000000000000000000000000000000000000000000000
;; val=1.836709923126491e60 guess=1.3552527156314762e30 x=100000000000000000000000000000000000000000000000000
;; val=4.591774807566227e59 guess=6.776263578526316e29 x=100000000000000000000000000000000000000000000000000
;; val=1.147943701641557e59 guess=3.388131790001028e29 x=100000000000000000000000000000000000000000000000000
;; val=2.8698592516038923e58 guess=1.6940658964762534e29 x=100000000000000000000000000000000000000000000000000
;; val=7.174648104009731e57 guess=8.470329511896057e28 x=100000000000000000000000000000000000000000000000000
;; val=1.7936620010024333e57 guess=4.23516481497761e28 x=100000000000000000000000000000000000000000000000000
;; val=4.484154752506097e56 guess=2.1175825255479648e28 x=100000000000000000000000000000000000000000000000000
;; val=1.12103843812658e56 guess=1.058791498892289e28 x=100000000000000000000000000000000000000000000000000
;; val=2.80259359531868e55 guess=5.293962216826523e27 x=100000000000000000000000000000000000000000000000000
;; val=7.006458988385903e54 guess=2.6469905531349943e27 x=100000000000000000000000000000000000000000000000000
;; val=1.751589747453284e54 guess=1.3235141659435625e27 x=100000000000000000000000000000000000000000000000000
;; val=4.378724382905143e53 guess=6.617948611847287e26 x=100000000000000000000000000000000000000000000000000
;; val=1.094431152807503e53 guess=3.3097298270516024e26 x=100000000000000000000000000000000000000000000000000
;; val=2.733580164225169e52 guess=1.6563756108519495e26 x=100000000000000000000000000000000000000000000000000
;; val=6.809041532376404e51 guess=8.312064444153693e25 x=100000000000000000000000000000000000000000000000000
;; val=1.6776222277853337e51 guess=4.216185749922949e25 x=100000000000000000000000000000000000000000000000000
;; val=3.958119299995747e50 guess=2.2266834754845036e25 x=100000000000000000000000000000000000000000000000000
;; val=7.89952169616626e49 guess=1.3378909408530375e25 x=100000000000000000000000000000000000000000000000000
;; val=8.715657894027273e48 guess=1.0426680099342613e25 x=100000000000000000000000000000000000000000000000000
;; val=1.746820421207371e47 guess=1.000873029120681e25 x=100000000000000000000000000000000000000000000000000
;; val=7.615151657380919e43 guess=1.0000003807575104e25 x=100000000000000000000000000000000000000000000000000
;; val=1.44761236415951e37 guess=1.0000000000000725e25 x=100000000000000000000000000000000000000000000000000
;; val=2.076918743413931e34 guess=1.0e25 x=100000000000000000000000000000000000000000000000000
;; val=2.076918743413931e34 guess=1.0e25 x=100000000000000000000000000000000000000000000000000
;; val=2.076918743413931e34 guess=1.0e25 x=100000000000000000000000000000000000000000000000000
;; val=2.076918743413931e34 guess=1.0e25 x=100000000000000000000000000000000000000000000000000
.....

x は 1.0e50 なので guess は十分に改善して答えが格納されていますが、チェックの値 val が 0.001 より小さくならず、guess の値も変化しなくなるため、この後は無限ループになります。

次は小さい値の場合。

gosh> (sqrt 0.000000000000000000000001)
;; val=1.0 guess=1.0 x=1.0e-24
;; val=0.25 guess=0.5 x=1.0e-24
;; val=0.0625 guess=0.25 x=1.0e-24
;; val=0.015625 guess=0.125 x=1.0e-24
;; val=0.00390625 guess=0.0625 x=1.0e-24
;; val=9.765625e-4 guess=0.03125 x=1.0e-24
0.03125

guess が十分に改善する前に、val が 0.001 未満となってしまいプログラムが終了してしまいます。

good-enough? を実装するもう一つの戦略は、ある繰返しから次への guess の変化に注目し、変化が予測値に比べ非常に小さくなった時に止めるのである。こういう終了テストを使う平方根手続きを設計せよ。これは小さい数、大きい数に対してうまく働くか。

(define (good-enough? guess new-guess)
  (< (abs (- guess new-guess)) 0.001))

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

guess の変化量を見るように改良しました。

大きい数字のとき

gosh> (sqrt 100000000000000000000000000000000000000000000000000)
1.0e25

デバッグ出力を入れていませんがプログラムは終了するようになります。

小さい数字のとき

gosh> (sqrt 0.000000000000000000000001)
0.001953125

改良前よりはよくなりましたが、guess の変化の許容値が 0.001 と被開平数(x)よりも大きいため、十分に guess が改善しないうちにプログラムは終了してしまいます。小さい数の場合は、guess の変化量を見るだけでは不十分で、guess の変化の許容値を被開平数(x)に合わせて調整する必要がありそうです。