Exercise 1.25: Alyssa P. Hacker complains that we went to a lot of extra work in writing expmod. After all, she says, since we already know how to compute exponentials, we could have simply written
(define (expmod base exp m)
(remainder (fast-expt base exp) m))
Is she correct? Would this procedure serve as well for our fast prime tester? Explain.
While the procedure is mathematically accurate and would produce the right results, fast-expt would produce enormous
numbers that would then have to be reduced modulo m. For example:
(expmod 2 10 7)
(remainder (fast-expt 2 10) 7)
(remainder 1024 7)
The 1024 might not seem so bad at first.
(remainder (fast-expt 2 10) 7)
(remainder 1267650600228229401496703205376 7)
That’s a bit excessive. The version bellow keeps the number in check.
(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))))
I am taking some liberty here in skipping a few minor steps.
(expmod 2 10 7)
(remainder (square (expmod 2 5 7)) 7)
(remainder (square (remainder (* 2 (expmod 2 4 7)) 7)) 7)
(remainder (square (remainder (* 2 (remainder (square (expmod 2 2 7)) 7)) 7)) 7)
(remainder (square (remainder (* 2 (remainder (square (remainder (square (expmod 2 1 7)) 7)) 7) 7) 7)) 7)
(remainder (square (remainder (* 2 (remainder (square (remainder (square (remainder (* 2 1) 7)) 7)) 7)) 7)) 7)
(remainder (square (remainder (* 2 (remainder (square (remainder (square (remainder 2 7)) 7)) 7)) 7)) 7)
(remainder (square (remainder (* 2 (remainder (square (remainder (square 2) 7)) 7)) 7)) 7)
(remainder (square (remainder (* 2 (remainder (square (remainder 4 7)) 7)) 7)) 7)
(remainder (square (remainder (* 2 (remainder (square 4) 7)) 7)) 7)
(remainder (square (remainder (* 2 2) 7)) 7)
(remainder (square (remainder 4 7)) 7)
(remainder (square 4) 7)
2
The key difference is that at no point do any of the numbers grow to be much larger than the base.