<< Previous exercise (1.16) | sicp-solutions | Next exercise (1.18) >>

An example for illustrating the algorithm: 3 * 10 = 3 * (2 * (10 / 2)) = 3 * (2 * 5) = 6 * 5 = 6 * (4 + 1) = 6 * 4 + 6 = 6 * (2 * (4 / 2)) + 6 = 6 * (2 * 2) + 6 = 6 * 2 * 2 + 6 = 12 * 2 + 6 = 24 + 6 = 30.

;; ex 1.17 ;; Assume double and halve are defined by the language (define (double x) (+ x x)) (define (halve x) (/ x 2)) (define (* a b) (cond ((= b 0) 0) ((even? b) (double (* a (halve b)))) (else (+ a (* a (- b 1)))))) ;; Testing (* 2 4) (* 4 0) (* 5 1) (* 7 10)

Here is an illustration of the recursive process:

; (fast-mult 3 7) ; (+ 3 (fast-mult 3 6)) ; (+ 3 (double (fast-mult 3 3)) ; (+ 3 (double (+ 3 (fast-mult 3 2)))) ; (+ 3 (double (+ 3 (double (fast-mult 3 1))))) ; (+ 3 (double (+ 3 (double (+ 3 (fast-mult 3 0)))))) ; (+ 3 (double (+ 3 (double (+ 3 0))))) ; (+ 3 (double (+ 3 (double 3)))) ; (+ 3 (double (+ 3 6))) ; (+ 3 (double 9)) ; (+ 3 18) ; 21

using tail recursion achieves better space order of growth of theta(1)

```
(define (fast-mult-by-add a b)
(define (double x) (+ x x))
(define (halve x) (/ x 2))
(define (helper a b product) ;; "add a" b times
(cond ((= b 0) product)
((even? b) (helper (double a) (halve b) product))
(else (helper a (- b 1) (+ a product)))))
(helper a b 0))
```

I agree with Bob. The problem instruction requires readers to implement a procedure analogous to fast-expt (from 1.2.4), which evolves into a recursive process, not an iterative one. Anyway, nice explanation.

Doesn't this accomplish the same thing but more efficiently? No need to delay the doubling.

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

I also made the master way. Not sure it changes about efficiency, but at least I find it more readable :)

I came up with the following solution, which seems to execute fewer calls than the solutions listed above:

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

For example if I calculate the product of 3 and 10,000,000, my solution uses 24 calls, while both of the solutions above use 32.

I like the modification by jazbot to call the procedure once instead of twice for odd b but i believe the procedure would throw an error for b=0. For most use cases, the condition of b=1 catches the reduction of b through the recursive process but if you start with b=0, then you should run into an issue.

Easily solved by adding in another condition though.

Isn't this version just skipping ahead to the next one, Exercise 1.18?