SICP問題1.36

SICP

修正した fixed-point

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (display next)
      (newline)
      (if (close-enough? guess next)
	  next
	  (try next))))
  (try first-guess))

x |-> log(1000)/log(x) の不動点を探索することで (x^2) = 1000 を求める。
まず平均緩和を使用使用しない場合

(fixed-point (lambda (x) (/ (log 1000) (log x))) 10)
; 2.9999999999999996 ; 1
; 6.2877098228681545 ; 2
; 3.7570797902002955 ; 3
; 5.218748919675316  ; 4
; 4.1807977460633134 ; 5
; 4.828902657081293  ; 6
; 4.386936895811029  ; 7
; 4.671722808746095  ; 8
; 4.481109436117821  ; 9
; 4.605567315585735  ; 10
; 4.522955348093164  ; 11
; 4.577201597629606  ; 12
; 4.541325786357399  ; 13
; 4.564940905198754  ; 14
; 4.549347961475409  ; 15
; 4.5596228442307565 ; 16
; 4.552843114094703  ; 17
; 4.55731263660315   ; 18
; 4.554364381825887  ; 19
; 4.556308401465587  ; 20
; 4.555026226620339  ; 21
; 4.55587174038325   ; 22
; 4.555314115211184  ; 23
; 4.555681847896976  ; 24
; 4.555439330395129  ; 25
; 4.555599264136406  ; 26
; 4.555493789937456  ; 27
; 4.555563347820309  ; 28
; 4.555517475527901  ; 29
; 4.555547727376273  ; 30
; 4.555527776815261  ; 31
; 4.555540933824255  ; 32
; 4.555532257016376  ; 33
; 4.555532257016376  ; 34

答えは正しいか?

(expt 4.555532257016376 4.555532257016376)
; 999.991323238027

ということで、OKそう。
次に平均緩和を使用使用する場合
平均緩和は y = x/y を y = 1/2(y + y/x)に単純に変換するヤツ y の次の予測値は y/x でなく 1/2(y + y/x)となるということ。
(両辺に y を足して 2 で割っている。)この場合だと元の式が
x = log(1000)/log(x)
なので、以下のようになる。
x = 1/2(x + log(1000)/log(x))

(fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 10)
; 6.5               ; 1
; 5.095215099176933 ; 2
; 4.668760681281611 ; 3
; 4.57585730576714  ; 4
; 4.559030116711325 ; 5
; 4.55613168520593  ; 6
; 4.555637206157649 ; 7
; 4.55555298754564  ; 8
; 4.555538647701617 ; 9
; 4.555536206185039 ; 10
; 4.555536206185039 ; 11

ステップ数は 34 => 11 ステップ数になった