Arantium Maestum

プログラミング、囲碁、読書の話題

SICPの勉強 問題1.45

SICP1.3.4の問題1.45を解いてみる。

average-dampとfixed-pointを使って任意のx、nにおけるxのn乗根の開方を求める。

average-dampを一回かけるだけの場合、y -> x/y3までは大丈夫だが y -> x/y4だと収束しない。

とりあえずaverage-dampを任意の回数繰り返す関数n-fold-average-dampを、これまでの問題で作った関数を組み合わせて作る:

(defn compose [f g]
  (fn [x] (f (g x))))

(defn repeated [f n]
  (if (>= 1 n)
    f
    (compose f (repeated f (dec n)))))

(defn average [x y]
  (/ (+ x y) 2))

(defn average-damp [f]
  (fn [x] (average x (f x))))

(defn n-fold-average-damp [f n]
  ((repeated average-damp n) f))

fixed-pointを直接使うと収束しない場合処理が止まらないので、iterateを使って任意の回数走らせて中間値がどう変わるか確認できるようにする:

(defn f [[x y]] 
  [x ((n-fold-average-damp (fn [z] (/ x (Math/pow z 32))) 4) y)])

(take 2 (drop 300000 (iterate f [10 1.0])))

32や4の部分を手で弄って試す。自動で表にするようなコードの方がエレガントだがめんどくさかった・・・

収束する条件としては、(fn [z] (/ x (Math/pow z p)))のpとaverage-dampを繰り返す回数rにおいて:

log2 p <= r

であるようだ。

それを踏まえて(そして過去に作ったfixed-pointを使って)nth-root関数を定義する:

(defn nth-root [n]
  (fn [x]
    (let [f         (fn [z] (/ x (Math/pow z (dec n))))
          avg-count (Math/floor (/ (Math/log (dec n)) (Math/log 2)))]
      (fixed-point 
        (fn [y] ((n-fold-average-damp f avg-count) y))
        1.0))))

(nth-root n)でn乗根を求める関数を作成する。例えば((nth-root 3) 10)で10の立方根が求められる。

匿名関数が三つ、微妙に違うclosureを持って作成されているというのは結構面白くもあり、脳内でイメージするのに一苦労でもあり。