1 (define (expt b n)
2   (if (= n 0)
3       1
4       (* b (expt b (- n 1)))))
5 (define (expt b n)
6   (expt-iter b n 1))
7 (define (expt-iter b counter product)
8   (if (= counter 0)
9       product
10       (expt-iter b
11 		 (- counter 1)
12 		 (* b product))))
13 (define (fast-expt b n)
14   (cond ((= n 0) 1)
15 	((even? n) (square (fast-expt b (/ n 2))))
16 	(else (* b (fast-expt b (- n 1))))))
17 (define (even? n)
18   (= (remainder n 2) 0))
19 
20 ;; 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 (b^(n/2))^2 = (b^2)^(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*b^n 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.) 
21 
22 (define (fast-expt-iter a b n)
23   (cond ((= n 0) a)
24 	((odd? n) (fast-expt-iter (* b a) b (- n 1)))
25 	((even? n) (fast-expt-iter a (square b) (/ n 2)))))
26 
27 (define (square x) (* x x))
28 (define (even? x) (= (remainder x 2) 0))
29 (define (odd? x) (= (remainder x 2) 1))
30 
31 (define (test-case actual expected)
32   (load-option 'format)
33   (format #t "Actual: ~A Expected: ~A" actual expected))
34 (test-case (fast-expt-iter 2 1 0) 2)
35 (test-case (fast-expt-iter 2 0 5) 0)
36 (test-case (fast-expt-iter 0 4 0) 0)
37 (test-case (fast-expt-iter 0 0 4) 0)
38 (test-case (fast-expt-iter 3 2 0) 3)
39 (test-case (fast-expt-iter 5 2 4) 80)
40 (test-case (fast-expt-iter 10 3 6) 7290)
41 (test-case (fast-expt-iter 8 4 3) 512)
42 
43 ;; these test cases wouldn't work
44 ;; (fast-expt-iter 2 0 0)
45 ;; (fast-expt-iter 0 0 0)