SICP Exercise 1.17

Question

The exponentiation algorithms in this section are based on performing exponentiation by means of repeated multiplication. In a similar way, one can perform integer multiplication by means of repeated addition. The following multiplication procedure (in which it is assumed that our language can only add, not multiply) is analogous to the expt procedure:

(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))

This algorithm takes a number of steps that is linear in $b$. Now suppose we include, together with addition, operations double, which doubles an integer, and halve, which divides an (even) integer by 2. Using these, design a multiplication procedure analogous to fast-expt that uses a logarithmic number of steps.

Answer

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

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

The result of a multiplication $ab$ is the same as $2a\frac{b}{2}$, which is what we are using here to achieve logarithmic order of growth. This halving of b (which is also the variable we are using as a counter) will be applied at least every other iteration, similar to exercise 1.16.