問題1.18

結論から行くと、問題1.16と同じような方法で解ける。なぜ、その方法が思いつくかと言うと、わからない(天才の脳を見てみたい)。

と言うことで、凡人の私は、問題1.16と同じ方法で、状態変数nを使って、ある量が一定になるようにしたら、答えが出てきました。

アルゴリズム

• bが偶数: n <- n, a <- 2a, b <- b/2
• bが奇数: n <- n + a, a <- a, b <- b-1

nを0に初期化して、bをカウントダウンして行く。

コード

(define (fast-mul-iter a b)
  (define (double n)
	(* n 2))
  (define (halve n)
	(/ n 2))
  (define (even? n)
	(= (remainder n 2) 0))
  (define (iter n a b)
	(cond ((= b 0) n)
		  ((even? b) (iter n (double a) (halve b)))
		  (else (iter (+ n a) a (- b 1)))))
  (iter 0 a b))

なんか根本的なところでしっくりきてない。