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