SICP 問題1.16
1.2.4 べき乗 - 計算機プログラムの構造と解釈 第二版
fast-exptのように, 逐次平方を使い, 対数的ステップ数の反復的べき乗プロセスを生成する手続きを設計せよ.
(ヒント: (b^(n/2))2 = (b^2)^(n/2)に注意し, 指数nと底bの他にもう一つの状態変数aを用意する.
状態の移変りで積abnが不変であるように状態遷移を定義する.
プロセス開始時にaを1とし, プロセス終了時にaが結果になるようにする.
一般に, 状態の移変りに不変のままの不変量 (invariant quantity)を定義する技法は, 反復的アルゴリズムの設計に有用である.)
fast-expt とは下のやつ。
(define (fast-expt b n)
(cond ((= n 0) 1)
((even? n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))
(define (even? n)
(= (remainder n 2) 0))
よくわからないけど、要は fast-expt は再帰的プロセスなので、それを反復的プロセスに書き直せってことなのかな？
この練習問題の少し上に書いてある対数的ステップ数ではない関数を再帰的プロセスから反復的プロセスに書き換えてる話があるので、それを確認してみる。
; 再帰的プロセス
(define (expt b n)
(if (= n 0)
1
(* b (expt b (- n 1)))))
; 反復的プロセス
(define (expt b n)
(expt-iter b n 1))
(define (expt-iter b counter product)
(if (= counter 0)
product
(expt-iter b
(- counter 1)
(* b product))))
ふむふむ。書いてみよう。
(define (even? n)
(= (remainder n 2) 0))
(define (fast-expt b n)
(fast-expt-iter b n 1))
(define (fast-expt-iter b count a)
(cond ((= count 1) a)
((even? count) (fast-expt-iter b
(/ count 2)
(* a (square b))))
(else (* b (fast-expt-iter b (- count 1) a)))))
※ trace で確認したいため、各関数は fast-expt のスコープの中に収めてません。
なんか違う。。。むずかしい。答え見よう。
; 解答例
(define (fast-expt b n)
(define (even? n)
(= (remainder n 2) 0))
(define (fast-expt-iter a b n)
(cond ((= n 0) a)
((even? n) (fast-expt-iter a (* b b) (/ n 2)))
(else (fast-expt-iter (* a b) b (- n 1)))))
(fast-expt-iter 1 b n))
なるほどー。
自分で書いたやつと引数の順番が違うのでわかりずらいけど、解答例を参考に上を書き直してみる。
(define (even? n)
(= (remainder n 2) 0))
(define (fast-expt b n)
(fast-expt-iter b n 1))
(define (fast-expt-iter b count a)
(cond ((= count 0) a)
((even? count) (fast-expt-iter (* b b)
(/ count 2)
a))
(else (fast-expt-iter b (- count 1) (* a b)))))
そうかそうか、基数の方変更していくのか。
難しい。。。