SICP解答メモ＆解説（問題１.6〜問題１.8）

SICP

問題1.6
新たに手続き「newif」を定義して実行すると、解釈系は「newif」を普通の手続きとして処理する。
解釈系は作用的順序の

  1. (good-enought? guess x)
  2. guess
  3. (sqrt-iter (improve guess x) x)
  4. newif

順で処理することになる。「new-if」の三番目の引数の「sqrt-iter」が再帰的に呼び出されるために、無限ループすることになる。
視覚的に表すと



(sqrt-iter (improve guess x) x)

             |

             (good-enought? guess x)

             guess

             (sqrt-iter (improve guess x) x)

			  |

			  (good-enought? guess x)

             		  guess

                          (sqrt-iter (improve guess x) x)

                                       |

				       …
となる。

問題1.6解答例@解答集

問題1.7

改良前ソース

(define (square x)
  (* x x))

(define (good-enought? guess x)
  (< (abs (- (square guess) x)) 0.0001))

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

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

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

(define (sqrt x)
  (sqrt-iter 1.0 x))
すごく大きい数で実行した時

具体的にどのくらい大きい数なら解答集のように無限ループするのか…んん、Gaucheの小数の扱いについてググってみたのだけれど、よくわからんかった。（たぶんfloatかdoubleのどちらかなのだろうけど。）
実際にやってみた。



gosh> (sqrt 10000000000000000000000000000000000000)

CALL sqrt-iter 1.0 10000000000000000000000000000000000000

 CALL sqrt-iter 5.0e36 10000000000000000000000000000000000000

  CALL sqrt-iter 2.5e36 10000000000000000000000000000000000000

   CALL sqrt-iter 1.25e36 10000000000000000000000000000000000000

    CALL sqrt-iter 6.25e35 10000000000000000000000000000000000000

                    ------無限ループ？------
となった。ぬうぅ…いまいちなぜ無限ループ（無限ループではないのかもしれないが）するのかピンとこない。もっと詳しくtraceしてみよう。


gosh> (sqrt 10000000000000000000000000000000000000)

CALL sqrt-iter 1.0 10000000000000000000000000000000000000

 CALL improve 1.0 10000000000000000000000000000000000000

 RETN improve 5.0e36

 CALL sqrt-iter 5.0e36 10000000000000000000000000000000000000

  CALL improve 5.0e36 10000000000000000000000000000000000000

  RETN improve 2.5e36

  CALL sqrt-iter 2.5e36 10000000000000000000000000000000000000

   CALL improve 2.5e36 10000000000000000000000000000000000000

   RETN improve 1.25e36

   CALL sqrt-iter 1.25e36 10000000000000000000000000000000000000

    CALL improve 1.25e36 10000000000000000000000000000000000000

    RETN improve 6.25e35

    CALL sqrt-iter 6.25e35 10000000000000000000000000000000000000

     CALL improve 6.25e35 10000000000000000000000000000000000000

     RETN improve 3.125e35

     CALL improve 3.125e35 10000000000000000000000000000000000000

     RETN improve 1.5625e35

     CALL improve 1.5625e35 10000000000000000000000000000000000000

     RETN improve 7.8125e34

     CALL improve 7.8125e34 10000000000000000000000000000000000000

     RETN improve 3.90625e34

     CALL improve 3.90625e34 10000000000000000000000000000000000000

     RETN improve 1.953125e34

     CALL improve 1.953125e34 10000000000000000000000000000000000000

                    ------無限ループ？------
どうもimproveで無限ループしているらしい。ふむふむ。でもなぜこうなるんだ…？解答集を見てみよう。

improve による推定値の改良は、一般的には有効数字の範囲内であるため、大きな数の場合、有効数字の範囲内での改良が、判定基準値を満すさず、無限ループになってしまう。

http://oss.timedia.co.jp/show/SICP/ex-1.7

とある。つまり「10×10＾36」は、有効数字の範囲外であるということか。有効数字は単精度浮動小数点数型（float型）では23ビット、倍精度浮動（ry（double型）では52ビットまで表現できる。つまりfloat型は「0〜8388607」まで、double型は「0〜4.503599627×10＾15」まで表すことができるということだ。とうことは、improveの計算がオーバーフローを起こして計算が終わらないということなのだろうか。結局いまいちよくわからないのであった。時間ができたらもう少し実験してみたいところ。

すごく小さい数で実行した場合



gosh> (sqrt 0.00000000000000000000000000000000001)

CALL sqrt-iter 1.0 1.0e-35

 CALL good-enought? 1.0 1.0e-35

 RETN good-enought? #f

 CALL sqrt-iter 0.5 1.0e-35

  CALL good-enought? 0.5 1.0e-35

  RETN good-enought? #f

  CALL sqrt-iter 0.25 1.0e-35

   CALL good-enought? 0.25 1.0e-35

   RETN good-enought? #f

   CALL sqrt-iter 0.125 1.0e-35

    CALL good-enought? 0.125 1.0e-35

    RETN good-enought? #f

    CALL sqrt-iter 0.0625 1.0e-35

     CALL good-enought? 0.0625 1.0e-35

     RETN good-enought? #f

     CALL good-enought? 0.03125 1.0e-35

     RETN good-enought? #f

     CALL good-enought? 0.015625 1.0e-35

     RETN good-enought? #f

     CALL good-enought? 0.0078125 1.0e-35

     RETN good-enought? #t

    RETN sqrt-iter 0.0078125

   RETN sqrt-iter 0.0078125

  RETN sqrt-iter 0.0078125

 RETN sqrt-iter 0.0078125

RETN sqrt-iter 0.0078125

0.0078125
ふむふむ…わからんwww。なぜこの値になってしまうのか。例によって解答集から。

xの値が判定基準値(この場合 1.0E-3)に比してずっと小さい場合、たとえば、x = 1.0E-6 であるような場合、理想的には、 (sqrt x) --> 1.0E-3 であるが guess の自乗が基準判定値より小さくなった時点で (good-enough? guess x) が真となるため、十分な推定値の改良がおこなわれずに終了してしまう。

http://oss.timedia.co.jp/show/SICP/ex-1.7

なるほど。この場合「0.0078125」の二乗が判定値の「0.001」より小さくなってしまうため、そこで計算が終了してしまう訳か。

good-enought?を改良する。

最初、

(define (good-enought? old new )
  (< (abs (- old new)) 0.0001))

と予測値との差を取ってどの程度変化したのかを見たのだが、うまく取れていないようで非常に大きい数などきちんとした値を計算することができなかった。そこで、解答集のとおりに

(define (good-enought? old new )
  (< (abs (- 1.0 (/ old new))) 0.0001))

除算を使っての変化をおった。その結果、うまく小さい数も大きい数も計算することができた。

あ〜あと、解答集の

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

での初期化がうまくいかなかったので

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

のようした。「old」の値を「2.0」にしたのは「old≠0」を満たせばどんな数でもいいと思う。たぶん…

数値計算難しいです。

問題1.8

問題文の通りにやったらできたでござる。

(define (cubic x)
  (cubic-iter 2.0 1.0 x))

(define (cubic-iter old new x)
  (if (good-enought? old new)
  new
  (cubic-iter new (improve new x) x)))

(define (good-enought? old new )
  (< (abs (- 1.0 (/ old new))) 0.0001))

(define (improve app x)
  (/ (+ (/ x (square app)) (* 2.0 app)) 3.0))

(define (square x)
  (* x x))

問題1.8解答例＠解答集