問題 1.18

無職の間にSICPも読んでみる。目標は焦らずしっかりと読む。問題の解答をさらす。解く順番は出来るだけリニア。

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

Exercise 1.18
Using the results of exercises 1.16 and 1.17, devise a procedure that generates an iterative process for multiplying two integers in terms of adding, doubling, and halving and uses a logarithmic number of steps.

O(log n) の手続きは n を一つずつ処理するのではなく、n / 2 で処理が進んでいく。その時に、n が偶数のときは準備、奇数のときは処理という感じで処理内容が変わる。割る２を繰り返すと、最終的に 2 -> 1 -> 0 のパターンが登場し、最終段階でかならず奇数（処理）が発生するのがポイント。考える時は単純なパターン 2n のパターンで考えると良い。

(define (even?  a)
  (= (remainder a 2) 0))

(define (double a)
  (+ a a))

(define (halve a)
  (/ a 2))

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