理系学生日記

おまえはいつまで学生気分なのか

問題1.16

逐次平方をつかって、対数的ステップ数の反復的べき乗を生成する.

(define (pow b n)
  (define (fast-iter-expt b n a)
    (define (even? n)
      (= (remainder n 2) 0))
    (cond ((= n 0) a)
          ((even? n) (fast-iter-expt (* b b) (/ n 2) a))
          (else (fast-iter-expt b (- n 1) (* a b)))))
  (fast-iter-expt b n 1))