問題1.16, p.26

サンプルコード

;code/problem-1-16.scm

(define (square x) (* x x))
(define (even? x) (= 0 (remainder x 2)))

(define (fast-expt b n)
    (cond ((= n 0) 1)
          ((even? n) (square (fast-expt b (/ n 2))))
          (else (* b (fast-expt b (- n 1))))))

(define (fast-expt2 a b n)
    (cond ((= n 0) 1)
          ((even? n) (square (fast-expt b (/ n 2))))
          (else (fast-expt (* a b) b (- n 1)))))

#?=(fast-expt 2 10)
#?=(fast-expt2 1 2 10)

fast-expt2が対数的ステップ数の反復的べき乗プロセスを生成する手続き。

実行例

#?="./problem-1-16.scm":16:(fast-expt 2 10)
#?-    1024
#?="./problem-1-16.scm":17:(fast-expt2 1 2 10)
#?-    1024