SICP Exercise 1.25

Question

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 well for our fast prime tester? Explain.

Answer

As a quick reminder, this is what our expmod function currently looks like:

(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))))

Much of the trouble with calculating Fermat’s Little Theorem for a big number comes from the fact that the number which we are trying to test is the exponent in the equation. As you remember, we tested numbers upwards of 1,000,000,000 in some of the previous exercises. So we have calculations like \(a^{1000000000}\), which is obviously a giant number, impossible for even a powerful computer to calculate in a realistic time frame.

But then why did our previous expmod function work so well? Shouldn’t we have the same problem there, too?

As it turns out, a clever trick is at play. As we see if we step through the iterations of the function, we are never actually calculating \(base^{exp}\). The only thing that is being squared is the modulo from a previous iteration, a much smaller number than the actual result of the exponentiation.