勉強ノート - SICP(1.5)
問題1.7が自分にとって異常に難しかったので1.6と併せてメモ。
問題1.6
ifを、condを利用して作った手続きで代用した場合の動作について。つまりifが特殊な形式である理由を理解するための問題。
(define (new-if predicate then-clause else-clause) (cond (predicate then-clause) (else else-clause)))
これを定義して、
(define (sqrt-iter guess x) (new-if (good-enough? guess x) guess (sql-iter (imporve guess x) x)))
この手続きを使用し平方根を求めようとした場合、どういう動きになるか。
答えは無限ループになって動かなくなる。なぜならifの場合は条件式がtrueの場合elseは評価されない*1んだけど、手続きの場合はすべての引数の評価をしてしまうから。
問題1.7
この問題で問題になっているプログラムはこちら。
この問題に対する設問は2つ。
- ここで定義されているsqrtに非常に小さい値 or 非常に大きい値を指定した場合、失敗する。どのように失敗するか例を挙げなさい。
- また、変化が予測値に比べ非常に小さくなったときに止まるように平方根手続きを設計しなさい。小さい値、大きい値を指定しても動くようにね！
設問1のすごく小さいケースは理解できた。大きいケースが分からないのでネットで調べたんだけど、設問2の回答例しか見つからない・・・。正直、設問2は簡単だからどうでも良い・・・。
小さいケース
問題はgood-enough?の定義。
(define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001))
予測値の誤差が0.001以下になった場合に終了する設計なので、0.0001の平方根が求められない。これはすぐに分かった。問題は次の大きすぎる場合。
大きいケース
海外のブログで回答を発見。
As the values grow larger, the precision of the guess comes into play. Eventually the computer becomes unable to represent the guess to a precision of 0.001. In such cases, the program can endlessly alternate between two guesses that are more than 0.001 away from the true square root.
Ken Dyck's Weblog » Blog Archive » Solution to SICP Exercise 1.7
・・・値が大きくなった場合、guessの精度が影響し始める。最終的にコンピュータは0.001を表せなくなるのだ。そのような場合、プログラムは正確な平方根から離れた0.001以上である2つの推測値の間を、果てしなく行き来することになる。
ってことで、無限ループします。
要するに桁落ちするわけです。(wikipedia:浮動小数点数)
IEEE 754形式の倍精度なので、仮数部52bit、指数部11bit。指数部は2の補数で表現されているので、10bit分の表現が出来る。・・・って所まで理解できたんだけど、ここで説明されている機械εが理解できない＞＜； くやしい＞＜；
要するに、
で変になる。
(define (^ x y) (* x (if (> y 1) (^ x (- y 1)) 1))) (sqrt (^ 2 42))
とかやると止まらなくなる。
修正版
(define (good-enough? guess x) (< (abs (- 1 (/ (square guess) x))) 0.0001))
という具合に、変化の割合を見ればOK。
*1:p10。「if式を評価するには、解釈系は式の述語
