[SICP 1.2.4] Exercise 1.17 Memo
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