SICP 問題 1.16 （逐次平方を使った末尾再帰のベキ乗計算）

【問題】
fast-exptのように、逐次平方をを使い、対数的ステップ数の反復的ベキ乗プロセスを生成する手続きを設計せよ。

ヒント：

(b^(n/2))^2 = (b^2)^(n/2)

に注意し、指数nと底bの他にもう一つの状態変数aを用意する。
状態の移り変わりで積ab^nが不変であるように状態遷移を定義する。
プロセス開始時にaを1とし、プロセス終了時にaが結果になるようにする。
一般に、状態の移り変わり不変のままの普遍量（invariant quantity）を定義する技法は、
反復的アルゴリズムの設計に有用である。

【解答】

いきなり記述されている「fast-expt」について、参考書の方でどう記述されていたかを載せよう。

;squareはなかったけど必要なので定義した。
(define (square x)
  (* x x))


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

これが末尾再帰になってないので末尾再帰にしてね、という問題だと思う。

末尾再帰のコツは、

１．終了時にはそれが答えになり、

２．かつ終了しない場合は再帰処理の材料になる

そういうモノを全て引数で渡していくように考えること。俺的に。
問題文のヒントにあるとおりに順番に考えていこう。

まず状態変数 a （つまりこれが上の１，２を満たす値になるわけだ）を用意するって話なので、今から定義していく関数のインタフェースはこんな感じになる。

(define (fast-expt2 b n a)
  なんらかの処理)

「何らかの処理」のところは、「ab^n」が不変になるようにするとのことなので、
とりあえずそう書いてみようか。

(define (fast-expt2 b n a)
  (* a (ベキ乗処理 b n)))

こんな感じ。「ベキ乗処理」やるなら再帰なので、ここで自分自身を呼び出す必要があるよね。

(define (fast-expt2 b n a)
  (* a (fast-expt2 b (- n 1) 次のa)))

「次のa」は、bをひとつ掛けた値になる。

(define (fast-expt2 b n a)
  (* a (fast-expt2 b (- n 1) (* a b))))

そうすると、「(* a (fast-expt2 b (- n 1) (* a b)))」の意味がわからんな。
最終的には、終了条件を満たした時に、aを返却すればいいんだから、
「(* a (fast-expt2 ...))」の、「(* a 」の部分は不要だなぁ。

(define (fast-expt2 b n a)
  (fast-expt2 b (- n 1) (* a b)))

お、すっきり。

じゃ、次に、終了条件を考えよう。これがないと終わらねーからな。
n=0の時に終了すればいいんだから、こう書ける。

(define (fast-expt2 b n a)
  (if (= n 0)
      a
      (fast-expt2 b (- n 1) (* a b))))

さて、これだと普通のベキ乗の計算を末尾再帰にしただけだな。
逐次平方を使うんだから、これにその概念を取り入れねば。

とりあえず、同じような形にしてみよう。

今作ったfast-expt2は n の比較を、「= 0 の場合」しか判別してないけど、
逐次平方ならば「偶数かどうか」という判別処理が必要になるから、
ifではなくてcondに変更してみる。

(define (fast-expt2 b n a)
  (cond ((= n 0) a)
        (else (fast-expt2 b (- n 1) (* a b)))))

じゃ、改めまして偶数判別のケースを入れてみる。

(define (fast-expt2 b n a)
  (cond ((= n 0) a)
        ((even? n) ここでうまい処理をする)
        (else (fast-expt2 b (- n 1) (* a b)))))

「ここでうまい処理をする」ってｗ

さて、どーすりゃいいんだろうなぁ。

元の処理は、「(square (fast-expt b (/ n 2)))」

となっているが、これだとfast-exptから戻ってきてから、squareしないとならん。
つまり末尾再帰じゃなくなってしまう。

あ！そうか、渡す b の値を２乗した値に変えちまえばいいんじゃね！！？

(define (fast-expt2 b n a)
  (cond ((= n 0) a)
        ((even? n) (fast-expt2 (* b b) (/ n 2) a))
        (else (fast-expt2 b (- n 1) (* a b)))))

できた〜。実行結果もＯＫっぽい。

gosh> (map (lambda (x) (fast-expt2 2 x 1)) (iota 20))

(1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288)

他の人の解答もおんなじ感じだ。