I am using the book SICP and attempting to solve this exercise:
1.2.4 Exponentiation
Exercise 1.18. 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
I am trying to solve this with the following code:
(define (double x)
(+ x x))
(define (halve x)
(floor (/ x 2)))
(define (* a b)
(define (iter count accumulate)
(cond ((= count 1) accumulate)
((even? a) (iter (halve count) (+ accumulate (double b))))
(else empty)))
(iter a 0))
As you might see, I am trying to deal with even numbers first. I am using the SICP wiki as my solutions-guide. They suggest some tests to see if the code works:
(* 2 4)
(* 4 0)
What I do not get is that my code passes on these two first tests, dealing only with even numbers.
However, when I try some big numbers which are multiples of two, the code fails. I checked the result using Python. For instance,
(IN PYTHON)
2**100
>> 1267650600228229401496703205376
2**98
>> 316912650057057350374175801344
a = 2**100
b = 2**98
a*b
>> 401734511064747568885490523085290650630550748445698208825344
When I use my function inside Dr. Racket with these values I get a different result:
(* 1267650600228229401496703205376 316912650057057350374175801344)
My result is: 63382530011411470074835160268800, which is wrong, as Python built-in functions suggest.
Why this is happening?
The recursive step seems wrong, and what's that empty doing there? also, what happens if b is negative? this solution should work:
(define (mul a b)
(define (iter a b acc)
(cond ((zero? b) acc)
((even? b) (iter (double a) (halve b) acc))
(else (iter a (- b 1) (+ a acc)))))
(if (< b 0)
(- (iter a (- b) 0))
(iter a b 0)))
For example:
(mul 1267650600228229401496703205376 316912650057057350374175801344)
=> 401734511064747568885490523085290650630550748445698208825344