;; 8/29/2012
;; Matthew Jenkins - github.com/jenkinsm
;; SICP - problem 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.

;; to recap: here was our final procedure for problem 1.16

(define (square n)
  (* n n))

(define (even? n)
  (= (remainder n 2) 0))

(define (expt-l b n)
  (expt-l-iter b n 1))

(define (expt-l-iter b n a)
  (cond ((= n 0) a)
	((even? n) (expt-l-iter (square b) (/ n 2) a))
	(else (expt-l-iter b (- n 1) (* a b)))))

;; and problem 1.17

(define (double n)
  (* n 2))

(define (halve n)
  (/ n 2))

(define (fast-mult a b)
  (cond ((= b 0) 0)
	((even? b) (double (fast-mult a (halve b))))
	(else (+ a (fast-mult a (- b 1))))))

;; and here's our iterative procedure.

;; question 1.16 states that a good way to think about iterative algorithms is
;; to find an invariant quantity - in 1.16 it was a*b^n, here it is a*b+c.

(define (log-mult a b)
  (log-iter-mult a b 0))

(define (log-iter-mult a b c)
  (cond ((= b 1) (+ a c))
	((even? b) (log-iter-mult (double a) (halve b)))
	(else (log-iter-mult a (- b 1) (+ c a)))))