SICP 練習問題 1.17 （逐次加算？を用いた乗算）

割とすんなりできたなぁ。


【問題】
本節のべき乗アルゴリズムは乗算の繰り返しによるべき乗の実行に基づいていた。
同様に整数の乗算を加算の繰り返しで実行できる。
次の乗算手続きは expt 手続きに似たものである。
（この言語には加算はあるが乗算はないと仮定する）

(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))

このアルゴリズムは b に雪景のステップ数をとる。
加算の他に、整数を2倍する double 演算と（偶数の）整数を２で割る halve 演算もあるとしよう。
これらを使い、fast-exptと類似の対数的ステップ数の乗算手続きを設計せよ。



【解答】
本練習問題の前に、参考書に記載されていた 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))))

さて、今回は掛け算を逐次平方のようなスタイルで実装するとのこと。
まずは double と halveを定義しよう。

(define (double x)
  (+ x x))

(define (halve x)
  (/ x 2))

これらを使って対数的ステップ数の乗算手続きを求めていく。
具体的に問題を解析してみよう。

a × b = a + a + a + ... + a  (※aをb回加算する）

b が偶数だったら、その後は b/2 回だけ a+a を加算していく処理にすればつじつまがあうよね。
b が奇数だったら、その時は a を加算して、その後は b-1 回だけ a を加算していく処理にすればOK。

で、末尾再帰に必要な、不変数（終了時はそれが解答になり、終了しない時は次の再帰処理での材料になるやつ）をaccm という名前にすると、上記の処理はこんな感じになる。

a    : 今回の加算値
b    : 残りの加算回数
a'   : 次回の加算値
b'   : 次回の加算回数
accm : 累計値

b が偶数の場合
a'   = a + a
b'   = b / 2
accm = accm

b が奇数の場合
a'   = a
b'   = b - 1
accm = accm + a

あとは、終了条件だが、これは b = 0 になった時に、accmを返せばいいだけ。

これそのまま実装していきゃできそうだな。

「*」を再定義するのはイヤなので、multiplyって名前にしてみる。

(define (multiply a b accm)
  (cond ((= b 0) accm)
        ((even? b) (multiply (double a) (halve b) accm))
        (else (multiply a (- b 1) (+ accm a)))))

できた～。


－