問題1.6、問題1.7 – SICP(計算機プログラムの構造と解釈)その2

問題1.6

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

new-if は通常の手続きのため、作用的順序の評価では引数が先に評価されるので、

(good-enough? guess x)

が真を返す場合でも

(sqrt-iter (improve guess x)
           x)

まで評価されるので、無限ループに陥る。

問題1.7

|guess2 - x| < 0.001 の時 good-enough? が真を返す。
x が非常に小さい時 guess2 < 0.001 => guess < √0.001 ≒ 0.03162 になると再帰が停止する。
x が非常に大きい時 桁数の増大により計算機が二値の比較の際に仮数部を無視するため、無限ループに陥る。

浮動小数点数 – Wikipedia

最初の good-enough? を使った mysqrt

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

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

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

;; good-enough? を使用
(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

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

改良した improved-good-enough? を使用した improved-mysqrt

(define (improved-good-enough? guess x)
  (< (abs (- 1.0 (/ guess (improve guess x)))) 0.001))

;; 改良型improved-good-enough? を使用
(define (improved-sqrt-iter guess x)
  (if (improved-good-enough? guess x)
      guess
      (improved-sqrt-iter (improve guess x) x)))

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

回答例の improved-good-enough2? を使用した improved-mysqrt2

(define (improved-good-enough2? old-guess new-guess)
  (< (abs (- 1.0 (/ old-guess new-guess))) 0.001))

;; 改良型improved-good-enough2? を使用
(define (improved-sqrt-iter2 old-guess new-guess x)
  (if (improved-good-enough2? old-guess new-guess)
      new-guess
      (improved-sqrt-iter2 new-guess (improve new-guess x) x)))

(define (improved-mysqrt2 x)
  (improved-sqrt-iter2 1.0 x x))

結果

(mysqrt 1.0E29)                      ;=> 無限ループに陥る
(improved-mysqrt 1.0E29)             ;=> 3.162281790337874e14
(improved-mysqrt2 1.0E29)            ;=> 3.162277660171076e14

(square (improved-mysqrt 1.0E29))    ;=> 1.0000026121502508e29
(square (improved-mysqrt2 1.0E29))   ;=> 1.0000000000017057e29

(mysqrt 1.0E-6)                      ;=> 0.031260655525445276
(improved-mysqrt 1.0E-6)             ;=> 0.0010005538710539446
(improved-mysqrt2 1.0E-6)            ;=> 0.0010000001533016628

(square (mysqrt 1.0E-6))             ;=> 9.772285838805523e-4
(square (improved-mysqrt 1.0E-6))    ;=> 1.0011080488810337e-6
(square (improved-mysqrt2 1.0E-6))   ;=> 1.0000003066033492e-6

(mysqrt 0.0004)                      ;=> 0.0354008825558513
(improved-mysqrt 0.0004)             ;=> 0.020001426615330147
(improved-mysqrt2 0.0004)            ;=> 0.020000000050877154

(square (mysqrt 0.0004))             ;=> 0.0012532224857331766
(square (improved-mysqrt 0.0004))    ;=> 4.000570666484372e-4
(square (improved-mysqrt2 0.0004))   ;=> 4.0000000203508615e-4
計算機プログラムの構造と解釈
ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542
«
»