SICP: Exercise 1.18

問題 1.18

問題 1.16、1.17 の結果を使い、加算、二倍、二分による、対数的ステップ数の、二つの整数の乗算の反復的プロセスを生成する手続きを工夫せよ。

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

問題 1.16、1.17

ochaochaocha3.hateblo.jp

ochaochaocha3.hateblo.jp

答え

(define (multiply-i a b)
  (define (double x) (* 2 x))
  (define (halve x) (/ x 2))
  (define (iter a b c) ;; a * b + c を一定にする
    (cond ((= b 0) c)
          ((even? b) (iter (double a) (halve c) c))
          (else (iter a (- b 1) (+ a c)))))
  (iter a b 0))

置換モデルで示す例

(multiply-i 4 5) ;;  a * b +  c
(iter 4 5 0)     ;;  4 * 5 +  0 = 20 +  0 = 20
(iter 4 4 4)     ;;  4 * 4 +  4 = 16 +  4 = 20
(iter 8 2 4)     ;;  8 * 2 +  4 = 16 +  4 = 20
(iter 16 1 4)    ;; 16 * 1 +  4 = 16 +  4 = 20
(iter 16 0 20)   ;; 16 * 0 + 20 =  0 + 20 = 20
20