根据书中给出的关系 \((b^{n/2})^2 = (b^2)^{n/2}\) ,并且使用一个不变量记录中间结果,写出对数步数内迭代计算幂的函数:
;;; 16-fast-expt.scm
(define (fast-expt b n)
(expt-iter b n 1))
(define (expt-iter b n a)
(cond ((= n 0)
a)
((even? n)
(expt-iter (square b)
(/ n 2)
a))
((odd? n)
(expt-iter b
(- n 1)
(* b a)))))
测试:
1 ]=> (load "16-fast-expt.scm")
;Loading "16-fast-expt.scm"... done
;Value: expt-iter
1 ]=> (fast-expt 2 0)
;Value: 1
1 ]=> (fast-expt 2 7)
;Value: 128
1 ]=> (fast-expt 2 10)
;Value: 1024