Iterative fast exponentiation

iter-fast-expt.lisp

(defun fast-exponential-iter (b n)
  (labels (
           (iter (a x n)
             ;; x to the power of n, with a being accumulator
             ;; the number a * x^n should always be constant
             ;;(format t "~&A: ~A ~&X: ~A  ~&N:~A ~&A*X^n: ~A" a x n (* a (expt x n)))
             (cond ((= n 1) (* a x))
                   ((evenp n) (iter a (square x) (/ n 2)))
                   (t (iter (* a x) x (- n 1))))))
    (iter 1 b n))) 

SICP3> (fast-exponential-iter 2 21)
A: 1 
X: 2  
N:21 
A*X^n: 2097152
A: 2 
X: 2  
N:20 
A*X^n: 2097152
A: 2 
X: 4  
N:10 
A*X^n: 2097152
A: 2 
X: 16  
N:5 
A*X^n: 2097152
A: 32 
X: 16  
N:4 
A*X^n: 2097152
A: 32 
X: 256  
N:2 
A*X^n: 2097152
A: 32 
X: 65536  
N:1 
A*X^n: 2097152
2097152