ochalog

RubyとMediaWikiとIRCが好き。

SICP: Exercise 1.17

問題 1.17

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

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

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

計算機プログラムの構造と解釈 第二版 1.2.4 べき乗」より

答え

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

置換モデルで示す例

(multiply 4 5)
(+ 4 (multiply 4 4))
(+ 4 (double (multiply 4 2)))
(+ 4 (double (double (multiply 4 1))))
(+ 4 (double (double (+ 4 (multiply 4 0)))))
(+ 4 (double (double (+ 4 0))))
(+ 4 (double (double 4)))
(+ 4 (double 8))
(+ 4 16)
20