SICP: Exercise 1.36

問題 1.36

問題 1.22 で示した基本の newline と display を使い、生成する近似値を順に印字するよう fixed-point を修正せよ。次に \( x \mapsto \log(1000)/\log(x) \) の不動点を探索することで、\( x^x = 1000 \) の解を見つけよ。（自然対数を計算する Scheme の基本 log 手続きを使う。）平均緩和を使った時と使わない時のステップ数を比べよ。（fixed-point の予測値を 1 にして始めてはいけない。\( \log(1) = 0 \) による除算を惹き起すからだ。）

「計算機プログラムの構造と解釈 第二版 1.3.3 一般的方法としての手続き」より

fixed-point の方は、printf デバッグのように display を追加するだけ。

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

平均緩和を行わない場合は

(define (f x)
  (/ (log 1000) (log x)))

(define (solve-x^x=1000)
  (fixed-point f 2.0))

(solve-x^x=1000)
; guess: 2.0, next: 9.965784284662087
; guess: 9.965784284662087, next: 3.004472209841214
; guess: 3.004472209841214, next: 6.279195757507157
; guess: 6.279195757507157, next: 3.759850702401539
; guess: 3.759850702401539, next: 5.215843784925895
; guess: 5.215843784925895, next: 4.182207192401397
; guess: 4.182207192401397, next: 4.8277650983445906
; guess: 4.8277650983445906, next: 4.387593384662677
; guess: 4.387593384662677, next: 4.671250085763899
; guess: 4.671250085763899, next: 4.481403616895052
; guess: 4.481403616895052, next: 4.6053657460929
; guess: 4.6053657460929, next: 4.5230849678718865
; guess: 4.5230849678718865, next: 4.577114682047341
; guess: 4.577114682047341, next: 4.541382480151454
; guess: 4.541382480151454, next: 4.564903245230833
; guess: 4.564903245230833, next: 4.549372679303342
; guess: 4.549372679303342, next: 4.559606491913287
; guess: 4.559606491913287, next: 4.552853875788271
; guess: 4.552853875788271, next: 4.557305529748263
; guess: 4.557305529748263, next: 4.554369064436181
; guess: 4.554369064436181, next: 4.556305311532999
; guess: 4.556305311532999, next: 4.555028263573554
; guess: 4.555028263573554, next: 4.555870396702851
; guess: 4.555870396702851, next: 4.555315001192079
; guess: 4.555315001192079, next: 4.5556812635433275
; guess: 4.5556812635433275, next: 4.555439715736846
; guess: 4.555439715736846, next: 4.555599009998291
; guess: 4.555599009998291, next: 4.555493957531389
; guess: 4.555493957531389, next: 4.555563237292884
; guess: 4.555563237292884, next: 4.555517548417651
; guess: 4.555517548417651, next: 4.555547679306398
; guess: 4.555547679306398, next: 4.555527808516254
; guess: 4.555527808516254, next: 4.555540912917957
; guess: 4.555540912917957, next: 4.555532270803653
4.555532270803653

となった。34 ステップ。

\( x \mapsto \log(1000)/\log(x) \) の不動点探索で平均緩和を行う場合は、本文にあるとおり両辺に \( x \) を足して 2 で割る。 $$ \frac{x + x}{2} = \frac{x + \log(1000)/\log(x)}{2} \quad \therefore\ x = \frac{x + \log(1000)/\log(x)}{2} $$

コードを書いて実行すると

(define (solve-x^x=1000-with-average-damping)
  (fixed-point (lambda (x)
                 (average x (f x)))
               2.0))

(solve-x^x=1000-with-average-damping)
; guess: 2.0, next: 5.9828921423310435
; guess: 5.9828921423310435, next: 4.922168721308343
; guess: 4.922168721308343, next: 4.628224318195455
; guess: 4.628224318195455, next: 4.568346513136242
; guess: 4.568346513136242, next: 4.5577305909237005
; guess: 4.5577305909237005, next: 4.555909809045131
; guess: 4.555909809045131, next: 4.555599411610624
; guess: 4.555599411610624, next: 4.5555465521473675
; guess: 4.5555465521473675, next: 4.555537551999825
4.555537551999825

となった。9 ステップと大幅にステップ数が縮まった。