SICP 問題1.36

2017/09/01

#sicp

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

近似値列の表示

練習問題1.22はどうやらスキップしたやつのようなので、newlineとdisplayを見てみる。
特に説明してるわけじゃないのか。調べたら名前の通りだった。

とりあえず修正前のfixed-pointを貼る。

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

表示するべき「生成する近似値列」はnextの中に入ってるのでそれを表示してやれば良さそう。

(define tolerance 0.000001)
(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))
; 2.0
; 1.5
; 1.6666666666666665
; 1.6
; 1.625
; 1.6153846153846154
; 1.619047619047619
; 1.6176470588235294
; 1.6181818181818182
; 1.6179775280898876
; 1.6180555555555556
; 1.6180257510729614
; 1.6180371352785146
; 1.6180327868852458
; 1.618034447821682
; 1.618033813400125
; 1.618033813400125

良いんじゃないでしょうか。

x^x = 1000 の解

$$ x \mapsto \frac{\log 1000}{\log x} $$

まずはこれの不動点を求める。

(fixed-point (lambda (x) (/ (log 1000) (log x))) 2.0)
; 9.965784284662087
; 3.004472209841214
; 6.279195757507157
; 3.759850702401539
; 5.215843784925895
; 4.182207192401397
; 4.8277650983445906
; 4.387593384662677
; 4.671250085763899
; 4.481403616895052
; 4.6053657460929
; 4.5230849678718865
; 4.577114682047341
; 4.541382480151454
; 4.564903245230833
; 4.549372679303342
; 4.559606491913287
; 4.552853875788271
; 4.557305529748263
; 4.554369064436181
; 4.556305311532999
; 4.555028263573554
; 4.555870396702851
; 4.555315001192079
; 4.5556812635433275
; 4.555439715736846
; 4.555599009998291
; 4.555493957531389
; 4.555563237292884
; 4.555517548417651
; 4.555547679306398
; 4.555527808516254
; 4.555540912917957
; 4.555532270803653
; 4.555537970114198
; 4.555534211524127
; 4.555536690243655
; 4.555535055574168
; 4.5555361336081
; 4.555535422664798
; 4.555535422664798

合ってるかわからん。

平均緩和を使って時とステップ数の比較

平均緩和の例のところによると、

(y = ½(y + x/y)が方程式y = x/yの単純な変換であることに注意しよう; これを得るには方程式の両辺にyを足して2で割る.)

とのことなので、今回の $$ x \mapsto \frac{\log 1000}{\log x} $$ の場合は、 $$ x \mapsto \frac{1}{2}(x + \frac{\log 1000}{\log x}) $$ を計算すればよいのかな。

; 使わない場合
(fixed-point (lambda (x) (/ (log 1000) (log x))) 2.0)
; 使った場合
(fixed-point (lambda (x) (/ (+ x (/ (log 1000) (log x))) 2)) 2.0)

こんなん？

ステップ数を数えるために、fixed-pointを少し修正した。

(define tolerance 0.000001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess cnt)
    (let ((next (f guess)))
      (display next)
      (display ":")
      (display cnt)
      (newline)
      (if (close-enough? guess next)
          next
          (try next (+ cnt 1)))))
  (try first-guess 0))

数える用変数のcntを追加。format的なもので表示する関数がschemeにもあるだろうけれど、ステップ数を確認するだけだし調べるのめんどいので今回はこれで。

それぞれの結果。

; 使わなかった場合
(fixed-point (lambda (x) (/ (log 1000) (log x))) 2.0)
; ...(略)...
; 4.555536690243655:36
; 4.555535055574168:37
; 4.5555361336081:38
; 4.555535422664798:39

; 使った場合
(fixed-point (lambda (x) (/ (+ x (/ (log 1000) (log x))) 2)) 2.0)
; ...(略)...
; 4.5555465521473675:7
; 4.555537551999825:8
; 4.555536019631145:9
; 4.555535758730802:10

ステップ数が1/2くらいになった。これで合ってるのか・・・？