SICP 問題 1.46 (反復改良法)

【問題】

本章に述べた数値計算法のいくつかは、反復改良法(iterative-improvement)という、非常に一般的な計算戦略の特殊化である。反復改良法では何かを計算するのに、答えに対する最初の予測値から始め、予測値が十分良好であるか調べ、そうでなければ予測値を改良し、改良した予測値を新しい予測値としてプロセスを続ける。
引数として2つの手続き:予測値が十分良好であるか調べる方法と、予測値を改良する方法をとる手続き iterative-improve を書け。
iterative-improve は引数として予測値をとり、予測値が十分良好になるまで改良を繰り返す手続きを値として返す。
iterative-improve を使って 1.1.7節の sqrt 手続きと、1.3.3節の fixed-point 手続きを書き直せ。

【解答】

う〜む。問題文がいまいち理解できねぇ。


引数として2つの手続き:予測値が十分良好であるか調べる方法と、予測値を改良する方法をとる手続き iterative-improve を書け。
 ↓

(define (iterative-improve [予測値が十分良好であるか調べる手続き]
			   [予測値を改良する方法])
  何らかの処理)

と読める。んが、次の一文を読むと、


iterative-improve は引数として予測値をとり、予測値が十分良好になるまで改良を繰り返す手続きを値として返す。
 ↓

(define (iterative-improve [予測値])
  [予測値が十分良好になるまで改良を繰り返す手続き])

どっちを考えりゃいいんだ?それとも問題文の解釈間違えてる?


あ!!



iterative-improve は、「引数として予測値をとり、予測値が十分良好になるまで改良を繰り返す手続き」を値として返す。
 ↓

(define (iterative-improve [予測値が十分良好であるか調べる手続き]
			   [予測値を改良する方法])
  ;予測値が十分良好になるまで改良を繰り返す処理
  (lambda ([予測値])
    [予測値が十分良好になるまで改良を繰り返す処理]))

この解釈だ!!あったまわり〜俺。
じゃ、すっきり解釈ができたところで解いていこう。

;反復改良法
(define (iterative-improve close-enough? improve)
  (lambda (first-guess)
    (let loop ((guess first-guess))
      (if #?=(close-enough? guess)
	  guess
	  (loop (improve guess))))))

これを使って sqrt と fixed-point を再実装すると。
まずは sqrt から。

;1.1.7節の sqrt 手続きを、iterative-improve を使って書き直し
(define (sqrt first-guess x)
  ;精度チェック手続き
  (define (close-enough? guess)
    (< (abs (- (* guess guess) x)) 0.00001))
  ;改良手続き
  (define (improve guess)
    (/ (+ guess (/ x guess)) 2))
  ;反復改良法を使う
  ((iterative-improve close-enough? improve) first-guess))

次、fixed-point 。

;1.3.3節の fixed-point 手続きを、iterative-improve を使って書き直し
(define (fixed-point f first-guess)
  ;精度チェック手続き
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2) ) 0.00001))
  ;改良手続き
  (define (improve guess)
    (f guess))
  ;反復改良法を使う
  ((iterative-improve close-enough? improve) (first-guess)))

う〜ん。。close-enough? 手続きをどう書いたらいいのやら。。


※2010/03/15追記
・・・このエントリを書いたのは昨日。そして解けたのは今朝。
朝、ベッドで目が覚めた時に思いついた。
なんでこんな簡単なことにきづかなかったんだ。。
fixed-point 手続きの定義はこうですね。

;1.3.3節の fixed-point 手続きを、iterative-improve を使って書き直し
(define (fixed-point f first-guess)
  ;精度チェック手続き
  (define (close-enough? guess)
    (< (abs (- guess (f guess)) ) 0.00001))
  ;改良手続き
  (define (improve guess)
    (f guess))
  ;反復改良法を使う
  ((iterative-improve close-enough? improve) (first-guess)))

黄金比を求めるアレを使って評価してみる。

;黄金比を求めるアレ
(define (fai x)
  (+ 1 (/ 1 x)))

で、実行。


gosh> (fixed-point fai 1.6)
1.6180371352785146
gosh>
アッテマス。