Laptops for Algernon

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