SICP Exercise 1.17 - 1.18

A multiplication procedure.

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

Exercise 1.17.
Rewrite to a code that uses a logarithmic number of steps.
(Use "double" and "halve".)

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

(define (double n)
  (+ n n))

(define (halve n)
  (/ n 2))

Exercise 1.18.
Rewrite to a code that generates an iterative process.

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

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

(define (double n)
  (+ n n))

(define (halve n)
  (/ n 2))