SICP 問題1.25

(define (expmod b e m)
  (cond ((= e 0) 1)
        ((even? e)
         (remainder (square (expmod b (/ e 2) m))
                    m))
        (else (remainder (* b (expmod b (- e 1) m))
                         m))))

(define (new-expmod base exp m)
  (remainder (fast-expt base exp) m))

time手続きを使って比較してみる．

gosh> (time (new-expmod 5 1000000 7))
;(time (new-expmod 5 1000000 7))
; real   5.010
; user   5.000
; sys    0.010
2
gosh> (time (expmod 5 1000000 7))
;(time (expmod 5 1000000 7))
; real   0.000
; user   0.000
; sys    0.000
2

expmodが逐次平方によって，その都度remainder手続きを適用することによって常に剰余を計算対象にしている．
new-expmodは5^1000000を計算するところまでのステップ数はべきに対して対数的に増加しているが，その後(remainder 5^1000000 7)の計算がO(n)となる．
途中計算の手間が大きいため高速素数テストと同じようには使えない．