問題1.7, p.14

まずは本文に載っている通りに実装してみる。

サンプルコード

;code/problem-1-7.scm

(load "./problem-1-3.scm")

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

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

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

(define (good-enough? guess x)
    (< (abs (- (square guess) x)) 0.001))

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

#?=(sqrt 2)
;#?=(sqrt 0.000002)
;#?=(sqrt 200000000000000000000)

実行結果

(sqrt 2) は1.4142156862745097と計算できるが、(sqrt 0.000002) は入力値が既に0.001より小さいため計算できない。また、(sqrt 200000000000000000000)では計算が終わらない。

問題文の通りに改良したコードを次に示す。このコードでは、述語good-enough?は、予測値の正解との差ではなく予測値の変化に注目する。

サンプルコード

;code/problem-1-7-2.scm

(define (sqrt-iter2 guess pre-guess x)
    (if (good-enough? guess pre-guess)
        guess
        (sqrt-iter2 (improve guess x) guess x)))

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

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

(define (good-enough? guess pre-guess)
    (< (/ (abs (- guess pre-guess)) guess) 0.001))

(define (sqrt x)
    (sqrt-iter2 1.0 100.0 x))

#?=(sqrt 2)
#?=(sqrt 0.000002)
#?=(sqrt 200000000000000000000)

実行結果

#?="./problem-1-7-2.scm":20:(sqrt 2)
#?-    1.4142135623746899
#?="./problem-1-7-2.scm":21:(sqrt 2.0e-6)
#?-    0.0014142135626178485
#?="./problem-1-7-2.scm":22:(sqrt 200000000000000000000)
#?-    1.4142135726118847e10

計算できている。