[SICP] 問題 1.16 : べき乗を求める反復的アルゴリズム

fast-exptのように, 逐次平方を使い, 対数的ステップ数の反復的べき乗プロセスを生成する手続きを設計せよ.

(ヒント: (b^n/2)² = (b²)^n/2に注意し, 指数nと底bの他にもう一つの状態変数aを用意する.
状態の移変りで積abⁿが不変であるように状態遷移を定義する.
プロセス開始時にaを1とし, プロセス終了時にaが結果になるようにする.
一般に, 状態の移変りに不変のままの不変量(invariant quantity)を定義する技法は, 反復的アルゴリズムの設計に有用である.)

問題文のヒントを参考に手続きを定義します.

(require (lib "racket/trace.ss"))

(define (square x) (* x x))

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

(define (fast-expt b n)
  (fast-expt-iter b n 1))

(trace fast-expt-iter)

p×bⁿを考え, pに結果をため込むようにします. 奇数と偶数の場合に分けて, pとbがどのように変化するかを考えます.

1) nが奇数の場合, n = m+1とする. 次の式が成立する.

p×b^m+1 = (p×b)×b^m

右辺のカッコ内の(p×b)が次のステップのpとなる.

2) nが偶数の場合, n = 2mとする. 次の式が成立する.

p×b^2m = p×(b²)^m

右辺のカッコ内の(b²)が次のステップのbとなる.

実行結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (fast-expt 2 8)
>(fast-expt-iter 2 8 1)
>(fast-expt-iter 4 4 1)
>(fast-expt-iter 16 2 1)
>(fast-expt-iter 256 1 1)
>(fast-expt-iter 256 0 256)
<256
256
> 

トレースの結果から, 反復的プロセスを生成しており, 対数的ステップ数で計算していることが分かります.