問題1.16

ベキ乗の計算でO(logn)で解く方法を再帰プロセスではなく、反復プロセスで解く方法。
反復プロセスにするのって、すごい難しい。この問題も全然思いつかず、つい答えを見てしまった。

ヒントにある通り、状態変数aを用意しておいて、a=b^0にセット。それで、反復の間にa=b^nにしてしまう方法を考える。この時に、a*(b^n)が常に一定になるようにする。と言うことで、最初0乗のものをどうやってn乗にするか、と言うのがポイント。上手く言葉では説明できないので、とりあえず表にしてみる。

2^10を計算する場合。

n	10	5	4	2	1	0
a	2^0	2^0	2^2	2^2	2^2	2^10
b	2^1	2^2	2^2	2^4	2^8	2^8
S	2^0*(2^1)^10	2^0*(2^2)^5	2^2*(2^2)^4	2^2*(2^4)^2	2^2*(2^8)^1	2^10*(2^8)^0

と言うような感じになる。
すなわち、

• nが偶数のとき。a <- a, b <- b^2, n <- n/2
• nが奇数のとき。a <- a*b, b <- b, n <- n-1

と言う感じ。

コードは、

(define (fast-iter b n)
  (define (square x)
	(* x x))
  (define (even? n)
	(= (remainder n 2) 0))
  (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))

となる。

今回は、答えを見ちゃったので、わかったけど、反復プロセスを設計するのは、難しいなぁ。
考え方の糸口すらもわからない場合がある。頭の回転が良くなりたいなぁ。今さら、無理なのかぁ。。。orz