計算機プログラムの構造と解釈
1.7
(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) (avarage guess (/ x guess))) (define (avarage x y) (/ (+ x y) 2)) (define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001)) (define (square x) (* x x)) ;上手くいかなくなる理由の説明 ;小さ過ぎる場合: (square (sqrt 0.001)) -> 0.001701185... (square (sqrt 0.0001)) -> 0.001043835... ;good-enough?では、予測値を2乗した数とその目的の値との差が、0.001以内 ;にあるがどうかで、その予測値が十分なものかどうかを判別している。した ;がって、目的の値が0.001付近、もしくはそれ以下の場合十分な値がとれる前 ;に予測値と目的値の値の差が0.001以下となり、計算が終了してしまう。 ;大きすぎる場合: (sqrt 10000000000000) -> 無限ループ (sqrt 12345678901234) -> 無限ループ ;14桁以上の整数となると、improveが小数点以下の位の限界により丸め誤差が ;発生し、返す値が収束してしまう。収束した時点での予測値の値が ;good-enough?で十分とされる誤差範囲内でない場合、同じ計算の繰り返しと ;なり、無限ループとなってしまう。 ;解決策の提示 ;解決策として、以下を提示する。 (define (new-sqrt x) (new-sqrt-iter 1.0 2.0 x)) (define (new-sqrt-iter guess old-guess x) (if (new-good-enough? guess old-guess) guess (new-sqrt-iter (improve guess x) guess x))) (define (new-good-enough? guess old-guess) (< (abs (- guess old-guess)) 0.0001)) ;guessの変移に注目し、それが0.0001以下になる時点で計算を終えている。 ;(improve guess x)の収束時点がどのような場合でも限界点である。 ;これは、小さい数に対しても大きい数に対してもある程度、より確からし ;くする。 (square (new-sqrt 0.001)) -> 0.0010000003699243661 (square (new-sqrt 0.0001)) -> 0.00010000000050981486 (square (new-sqrt 10000000000000)) -> 10000000000000.002 (square (new-sqrt 12345678901234)) -> 12345678901234.002
1.8
立方根、これは簡単
(define (cube-root x) (cube-root-iter 1.0 2.0 x)) (define (cube-root-iter guess old-guess x) (if (good-enough? guess old-guess) guess (cube-root-iter (improve guess x) guess x))) (define (improve guess x) (/ (+ (/ x (square guess)) (* 2 guess)) 3)) (define (good-enough? guess old-guess) (< (abs (- guess old-guess)) 0.0001)) (define (square x) (* x x)) (define (pow x y) (if (<= y 1) x (* x (pow x (- y 1))))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (pow (cube-root 8) 3) -> 8.000000000144743 (pow (cube-root 3) 3) -> 3.0000000000002074 (pow (cube-root 123456789012345) 3) -> 123456789012344.95 ;;↑微妙だが数が大きいので相対的に誤差は小さいとし、良しとする。 (pow (cube-root 0.0001) 3) -> 0.00010000000152937715
こんな感じでいいはず