SICP: Exercise 1.17
問題 1.17
本節のべき乗アルゴリズムは、乗算の繰返しによるべき乗の実行に基づいていた。同様に整数の乗算を加算の繰返しで実行出来る。次の乗算手続きは(この言語には加算はあるが、乗算はないと仮定する)
expt
手続きに似たものである:(define (* a b) (if (= b 0) 0 (+ a (* a (- b 1)))))
このアルゴリズムは
b
に線形のステップ数をとる。加算の他に整数を二倍するdouble
演算と(偶数の)整数を2で割るhalve
演算もあるとしよう。これらを使い、fast-expt
と類似の対数的ステップ数の乗算手続きを設計せよ。
答え
(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