問題1.16

逐次平方の反復的プロセスバージョンを求めよ

発想の転換が必要。

b^n = (b^(n/2))^2 = (b^2)^(n/2)
b^n = b * b^(n-1)

[普通の逐次平方ならばこんな感じ]
2^6
= (2^3)^2
= 8^2
= 8 * 8
= 64

[反復プロセスで行うならばこうする]
2^6
= (2^3)^2
= (2^2)^3 --> n, a では無く、bを変えるのがポイント
= 4^3
= 4 * 4^2

; 逐次平方
; Θ(log n)ステップ、Θ(1)スペース
(define (fast-expt2 b n)
  (define (iter b n a)
    (cond ((= n 0) a)
	  ((even? n) (iter (square b) (/ n 2) a))
	  (else (iter b (- n 1) (* a b)))))
  (iter b n 1))

(define (even? n)
  (= (remainder n 2) 0))

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