<< Previous exercise (1.15) | sicp-solutions | Next exercise (1.17) >>
;; 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)
(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.