## [SICP 1.2.4] Exercise 1.17 Memo

5-12-2014

**Exercise 1.17. Using the results of exercises 1.16 and 1.17, devise a procedure that generates an iterative process for multiplying two integers in terms of adding, doubling, and halving and uses a logarithmic number of steps.**

In the exercise, the multiplication is implemented as follows:

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

This requires the order of b. The question here is that we want to implement the same function that requires the order proportional to some logarithm.

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

This only requires the order of log_2(b).

As a result, we get the following output:

(mul-1 100 5000000) ; memory shortage (mul-2 100 5000000) ; 500000000 (mul-2 10000 50000000000000) ; 500000000000000000