Arantium Maestum

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

SICPの勉強 問題1.16

SICP1.2.4の問題1.16を解いてみる。

(defn fast-exp-iter [b n]
  (loop [n n x 1 y b z 1]
    (cond
      (zero? n)     z
      (< n (* 2 x)) (recur (- n x) 1 b (* y z))
      :else         (recur n (* 2 x) (* y y) z))))

引数名が考えつかなかった、というのはいつもの弁。

n = 2a1 + 2a2 ... 2an (a1 > a2 > ... > an)

と考えて、bにa1回二乗し続けたものと、a2回二乗し続けたものと...を全て掛け合わせている。

よりclojure的に書くとしたらreductionsか何かでnからa1...anのリストを作成して、

(apply * (map #(take % (iterate sq b)) a-list))

になるだろうか。もちろん(defn sq [x] (* x x))である。