Skip to content
Find file
Fetching contributors…
Cannot retrieve contributors at this time
31 lines (26 sloc) 876 Bytes
(define (even? n) (= 0 (remainder n 2)))
;; linear recursion
(define (expmod base exp m)
(display ".")
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
;; tree recursion
(define (expmod base exp m)
(display ".")
(cond ((= exp 0) 1)
((even? exp)
(remainder (* (expmod base (/ exp 2) m)
(expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
;; compared to using square, using inlined multiplication does not
;; result in twice as many calls to expmod. Instead it results in
;; exponential growth because the entire subtree has to be recomputed
;; twice at each level.
Jump to Line
Something went wrong with that request. Please try again.