sicp exercise 1.16

;  Exercise 1.16. Design a procedure that evolves an iterative exponentiation process that uses successive
;  squaring and uses a logarithmic number of steps, as does fast-expt. (Hint: Using the observation that
;  (bn/2)2 = (b2)n/2, keep, along with the exponent n and the base b, an additional state variable a, and
;  define the state transformation in such a way that the product a bn is unchanged from state to state.
;  At the beginning of the process a is taken to be 1, and the answer is given by the value of a at the
;  end of the process. In general, the technique of defining an invariant quantity that remains unchanged
;  from state to state is a powerful way to think about the design of iterative algorithms.)


(define (square1 a) (* a a))

(define (fast-exp-recur base exp)
        (cond ((= exp 0) 1)
              ((even? exp) (square1 (fast-exp-recur base (/ exp 2))))
              (else (* base (fast-exp-recur base (- exp 1))))))


;(display (fast-exp-recur 2 8)) (newline)
;(display (fast-exp-recur 2 9)) (newline)
;(display (fast-exp-recur 34 542)) (newline)
;(display (fast-exp-recur 542  7766)) (newline)
;(display (fast-exp-recur 7766 88223)) (newline)

; took 30.796 secs to finish
;(display (fast-exp-recur 9999 999999)) (newline)

(display "----------------------")(newline)


(define (fast-exp-iter base exp)
    (define (func n b res)
            (cond ((= n 0) res)
                  ((even? n) (func (/ n 2) (square1 b) res))
                  (else (func (- n 1) b (* res b)))))
    (func exp base 1))


;(display (fast-exp-iter 2 8)) (newline)
;(display (fast-exp-iter 2 9)) (newline)
;(display (fast-exp-iter 34 542)) (newline)
;(display (fast-exp-iter 542  7766)) (newline)
;(display (fast-exp-iter 7766 88223)) (newline)

; took 32.165 secs to finish :(
; iterative is supposed to be faster, some problem in my implementation
(display (fast-exp-iter 9999 999999)) (newline)