练习 1.16

根据书中给出的关系 \((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

讨论

blog comments powered by Disqus