SICP 問題1.17

2017/08/24

#sicp

本節のべき乗アルゴリズムは, 乗算の繰返しによるべき乗の実行に基づいていた.
同様に整数の乗算を加算の繰返しで実行出来る.
次の乗算手続きは(この言語には加算はあるが, 乗算はないと仮定する)expt手続きに似たものである:

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

このアルゴリズムはbに線形のステップ数をとる.
加算の他に整数を二倍するdouble演算と(偶数の)整数を2で割るhalve演算もあるとしよう.
これらを使い, fast-exptと類似の対数的ステップ数の乗算手続きを設計せよ.

とりあえずdouble演算とhalve演算を定義する。
halve演算に関しては、偶数じゃない場合何を返せば良いのかわからんが、halveを呼ぶ前に偶数チェックをしてそもそも偶数の時にしか呼ばないようにしよう。

(define (double a)
  (+ a a))

(define (halve a)
  (/ a 2))

除算を使っていいのかは謎だけど、問題文では乗算しか禁止されてないっぽいから一旦はこれで進めよう。

再帰的プロセスのほうが直感的に考えられるので、まずは問題点を把握する意味でも難易度の低い再帰的プロセスで考える。

a * b というのは、(aを倍にしたもの) * b/2に読み替えられる。(double a) * (halve b)ということ。
また、上記も同じ公式が適用されるので、 (double (double a)) * (halve (halve b)) と続いていくので、普通に再帰でかけそう。

ただしこれはbが偶数の場合だけなので、奇数の場合は別のことを考える必要がある。
奇数の場合は、bから1引いて、その分aを足せばよい。(b - 1) + a

とりあえずここらへんまでの考えでコードかけそうなので、書いてみる。

(define (fast-multi a n)
  (cond ((= n 0) 0)
        ((even? n) (fast-multi (double a) (halve n)))
        (else (+ a (fast-multi (double a) (halve (- n 1)))))))

ちゃんと動いたっぽい。
次にこれを反復的プロセスに書き直す。

(define (fast-multi a n)
  (fast-multi-iter a n 0))

(define (fast-multi-iter a n x)
  (cond ((= n 0) x)
        ((even? n) (fast-multi-iter a (halve n) (+ x (double a))))))
  ; モゴモゴモゴ

あれ、なんか書けない。
一旦対数的ステップ数じゃない、普通の反復的プロセスで書いてみる。

(define (fast-multi a n)
  (fast-multi-iter a n 0))

(define (fast-multi-iter a n x)
  (cond ((= n 0) x)
        (else (fast-multi-iter a (- n 1) (+ x a)))))

うん。

(define (fast-multi a n)
  (fast-multi-iter a n 0))

(define (fast-multi-iter a n x)
  (cond ((= n 0) x)
        ((even? n) (fast-multi-iter (double a) (halve n) x))
        (else (fast-multi-iter a (- n 1) (+ x a)))))

書けた！
先に反復的プロセスで考えてから対数的ステップ数に書き直すほうが考えやすいかも。

ちなみに模範解答は下記。

(define (double x) (+ x x))
(define (halve x) (/ x 2))

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

こっち変数1個少ないし、関数も1個少ない。
僕は固定概念に囚われていたのかもしれない。