SICP: Exercise 1.16

問題 1.16

fast-expt のように、逐次平方を使い、対数的ステップ数の反復的べき乗プロセスを生成する手続きを設計せよ。（ヒント：\( \left( b^{ \frac{n}{2} } \right)^2 = (b^2)^\frac{n}{2} \) に注意し、指数 \( n \) と底 \( b \) の他にもう一つの状態変数 \( a \) を用意する。状態の移変りで積 \( ab^n \) が不変であるように状態遷移を定義する。プロセス開始時に \( a \) を 1 とし, プロセス終了時に \( a \) が結果になるようにする。一般に、状態の移変りに不変のままの不変量 (invariant quantity) を定義する技法は、反復的アルゴリズムの設計に有用である。)

「計算機プログラムの構造と解釈 第二版 1.2.4 べき乗」より

答え

(define (fast-expt-i b n)
  (define (iter a b n)
    (cond ((= n 0) a)
          ((even? n) (iter a
                           (square b)
                           (/ n 2)))
          (else (iter (* a b)
                      b
                      (- n 1)))))
  (iter 1 b n))

置換モデルで示す例

\( ab^n \) が一定になることに注意。

(fast-expt-i 2 5) ;; ab^n
(iter 1 2 5)      ;; 32
(iter 2 2 4)      ;; 32
(iter 2 4 2)      ;; 32
(iter 2 16 1)     ;; 32
(iter 32 16 0)    ;; 32
32