Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
19 lines (17 sloc) 640 Bytes
;Alyssa P. Hacker版本
(define (expmod base exp m)
  (remainder (fast-expt base exp) m))

;原始版本
(define (expmod base exp m)
  (cond 
    ((= exp 0) 1)
    ((even? exp)
      (remainder (square (expmod base (/ exp 2) m)) 
                 m))
    (else
      (remainder (* base (expmod base (- exp 1) m))
                 m))))

Alyssa P. Hacker该写后的expmod方法时间复杂度虽然和之前的类似,这里的主要问题是baseexp的值可能很大,如果超出了scheme整型数的范围,那么程序是会出错的。 而原始版本,由于是取模后再平方,就能避免这个问题。