計算機プログラムの構造と解釈

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

こんな感じでいいはず