Multiplication in terms of addition Given the following task:


  Exercise 1.17
  
  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.


I wrote this solution:

(define (double a) (* a 2))
(define (halve a) (/ a 2))
(define (even n) (= (remainder n 2) 0))

(define (times a b)
  (cond ((= 1 b) a)
        ((even b) (times (double a) (halve b)))
        (else (times (+ a a) (- b 1)))))


What do you think?
Your implementation will not produce correct results in general.

In the base case of b = 0, result should be 0.  In the case of even b, result is double a times half b (which you have done correctly).  In the case of odd b, result should be a + (double a times half (b - 1)).

(define (times a b)
  (cond ((= 0 b) 0)
        ((even b) (times (double a) (halve b)))
        (else (+ a (times (double a) (halve (- b 1)))))))


To make this definition iterative, add an accumulator, like so:

(define (times a b)
  (times-iter 0 a b))

(define (times-iter acc a b)
  (cond ((= 0 b) acc)
        ((even b) (times-iter acc (double a) (halve b)))
        (else (times-iter (+ a acc) (double a) (halve (- b 1))))))