[SICP] 問題 1.18 : 対数的ステップ数の乗算手続き（反復的プロセス）

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

問題 1.16の結果を参考にして手続きを定義します. 0や負の数をかけた場合の扱いは, ループに入る前に判定してます.

(require (lib "racket/trace.ss"))

(define (double x) (* x 2))

(define (halve x) (/ x 2))

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

(define (fast-mult a b)
  (cond ((< b 0) (* -1 (fast-mult-iter a (abs b) 0)))
        ((= b 0) 0)
        (else (fast-mult-iter a b 0))))

(trace fast-mult-iter)

p+a×bを考え, pに計算の途中経過をため込むことにします. pを0から始めます. p + a×bの計算について, 奇数と偶数の場合に分けて, 計算をどのように進めるかを考えます.

1) bが奇数の場合, b = m+1とする. 次の式が成立する.

p + a×(m+1) = (p+a) + (a×m)

(p+a)が次のpとなります.
2) nが偶数の場合, b = 2mとする. 次の式が成立する.

P + a×(2m) = p + double(a)×m

double(a)が次のaとなります.

実行結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (fast-mult 3 45)
>(fast-mult-iter 3 45 0)
>(fast-mult-iter 3 44 3)
>(fast-mult-iter 6 22 3)
>(fast-mult-iter 12 11 3)
>(fast-mult-iter 12 10 15)
>(fast-mult-iter 24 5 15)
>(fast-mult-iter 24 4 39)
>(fast-mult-iter 48 2 39)
>(fast-mult-iter 96 1 39)
>(fast-mult-iter 96 0 135)
<135
135
> (fast-mult 4 0)
0
> (fast-mult 5 -8)
>(fast-mult-iter 5 8 0)
>(fast-mult-iter 10 4 0)
>(fast-mult-iter 20 2 0)
>(fast-mult-iter 40 1 0)
>(fast-mult-iter 40 0 40)
<40
-40
> 

トレースの結果から, 反復的プロセスを生成していることが分かります.