SICP Exercise 1.18

Question

Using the results of Exercise 1.16 and Exercise 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.

Answer

copy(define (double x) (* 2 x))
(define (halve x) (/ x 2))
(define (even? x) (= (remainder x 2) 0))

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

The footnote suggests that we can use something called the “Russian peasant multiplication”, also known as Egyptian or Ethiopian multiplication, to achieve this. The method is simple, yet intricate: halve the first operand (rounding down to the nearest integer if odd) and double the second operand until the first operand reaches $1$. If the first operand is odd, add the associated value of the second operand to the result.

An example multiplication ($21\times 5$) looks as follows:

$$215$$ $$\cancel{1010}$$ $$520$$ $$\cancel{240}$$ $$180$$ $$80+20+5=105$$

Johnny Ball can explain this much better than I could, so I recommend watching his explanation if you want to understand why this works.