Skip to content
Find file
Fetching contributors…
Cannot retrieve contributors at this time
22 lines (14 sloc) 475 Bytes
(define (square x) (* x x))
(define (even? n) (= (remainder n 2) 0))
;; linear recursive algorithm
(define (fast-expt b n)
(cond ((= n 0) 1)
((even? n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))
;; iterative algorithm
(define (expt b n)
(fast-expt-iter b n 1))
(define (fast-expt-iter b n a)
(cond ((= n 0) a)
((even? n) (fast-expt-iter (square b) (/ n 2) a))
(else (fast-expt-iter b (- n 1) (* b a)))))
Something went wrong with that request. Please try again.