# sicp-ex-1.17

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 (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))

```

bob

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

ybsh

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.

master

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))))))
```

bidouille

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