# sicp-ex-1.16

```
;; ex 1.16

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

(define (square x) (* x x))

;; Testing

(fast-expt 2 0)
(fast-expt 2 1)
(fast-expt 2 2)
(fast-expt 2 4)
(fast-expt 2 8)
(fast-expt 2 16)

(fast-expt 2 3)
(fast-expt 2 5)
(fast-expt 2 10)
(fast-expt 2 20)

```

another solution

```
(define (fast-expt b n)
(define (cube x) (* x x x))
(define (fast-expt-iter b a counter)
(cond ((= counter 0) a)
((= counter 1) (* a b))
((even? counter) (fast-expt-iter
(square b)
(* (square b) a)
(- (/ counter 2) 1)))
(else (fast-expt-iter
(square b)
(* (cube b) a)
(- (/ (- counter 1) 2) 1)))))
(fast-expt-iter b 1 n))
```

[Owen]: The first implementation is really smart and I want to give a brief explanation for that.

The idea is that: During the whole process, a * b^n always equal to b^k, where a, b, n are the variables in the procedure (iter a b n) and k is the desired exponent from user input.

One can easily get a brief idea by trying some easy cases, say b^6.

I believe a formal proof of the correctness of this program can be given with induction. By first proving the correctness when k = 0, 1 and 2. I did the proof by myself but can't post latex here, maybe someone can share a link.