So, let's try to use it for the 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.
; code
(define (fast-expt b n)
(define (iter a b n)
(cond
((= n 1) (* a b))
((even? n) (iter a (* b b) (/ n 2)))
(else (iter (* a b) b (- n 1)))))
(iter 1 b n))
; tests
(load "test-manager/load.scm")
(define-each-test
(assert= 1 (fast-expt 2 0))
(assert= 2 (fast-expt 2 1))
(assert= (expt 2 8) (fast-expt 2 8))
(assert= (expt 2 6) (fast-expt 2 6)))
(run-registered-tests)
Run:
mit-scheme < ex1_16.scm
1 ]=> (run-registered-tests)
Oops! I completely forgot about condition when the exponent n is zero.
Fix it:
(define (fast-expt b n)
(define (iter a b n)
(cond
((= n 0) a)
((even? n) (iter a (* b b) (/ n 2)))
(else (iter (* a b) b (- n 1)))))
(iter 1 b n))
Run it again:
1 ]=> (run-registered-tests)....
4 tests, 0 failures, 0 errors.
That's it!
