Name: Anonymous 2009-06-01 20:26
Oh wise Lispers and Conjurers of /prog/, I, humble Nubi, seek your enlightenment. I have started reading SICP, but I'm stuck on an exercise. I have figured out how to make fast-mult into a logarithmic process, but how do I make it into a tail recursion as well as a logarithmic process? Here is my code:
; SICP exercise 1-13
; Peasant's algorithm for multiplication
; write a logarithmic iterative process for mult
(define (fast-mult a b)
(cond ((= b 0) 0)
((even? b) (double (fast-mult a (halve b))))
(else (+ a (fast-mult a (- b 1))))))
(define (double a) (+ a a))
(define (halve a) (/ a 2))
(define (fast-mult2 a b)
(fast-mult-iter a a b))
(define (fast-mult-iter a n b)
(cond ((= b 1) n)
((and (even? b) (> b 2))
(fast-mult-iter a (double n) (halve b)))
(else (fast-mult-iter a (+ a n) (- b 1)))))
(fast-mult 3 2)
(fast-mult2 3 2)
(fast-mult 3 3)
(fast-mult2 3 3)
(fast-mult 3 4)
(fast-mult2 3 4)
(fast-mult 3 5)
(fast-mult2 3 5)
(fast-mult 3 6)
(fast-mult2 3 6)