問題 1.17

無職の間にSICPも読んでみる。目標は焦らずしっかりと読む。問題の解答をさらす。解く順番は出来るだけリニア。

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

(define (* a b)

  (if (= b 0)

      0

      (+ a (* a (- b 1)))))

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

Exercise 1.17
The exponentiation algorithms in this section are based on performing exponentiation by means of repeated multiplication. In a similar way, one can perform integer multiplication by means of repeated addition. The following multiplication procedure (in which it is assumed that our language can only add, not multiply) is analogous to the expt procedure:

This algorithm takes a number of steps that is linear in b. Now suppose we include, together with addition, operations double, which doubles an integer, and halve, which divides an (even) integer by 2. Using these, design a multiplication procedure analogous to fast-expt that uses a logarithmic number of steps.

ノートに計算過程をまとめながら、考えたらできた。

a * b を計算する場合、 a を２倍、 b を 1/2 しながら進行していく。その過程で、b が奇数の場合の a をすべて足し算すればOK。
例えば、1 * 12 の場合は下記のようになる。カッコに囲まれているのが足し算する箇所。

b: 12 11 10 09 08 07 06 05 04 03 02 01 00
a:  1                 2       [ 4 ] [ 8 ]

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

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

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

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