SICP Exercise 1.25: A Simpler expmod?

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.

Yes. And no.

Yes, we could have written what Alyssa P. Hacker suggests and it would have successfully performed the prime test. But no, it wouldn't serve as well for our fast prime tester - it would have taken much longer to perform the test.

Why? Well, as I discussed in my solution to exercise 1.24, once the numbers exceed a certain value (2³⁰ on my interpreter) the interpreter needs to use a different representation that can handle larger values. And when it does this, the performance of the calculations degrades. In this case we're raising numbers to powers over 1,000, 10,000, etc, and so we'll quickly reach the point where this change occurs.

Here's what happened when I plugged it into my code from exercise 1.24:

> (timed-prime-test 1009)
1009 *** 47611.0
> (timed-prime-test 1013)
1013 *** 49780.0
> (timed-prime-test 1019)
1019 *** 49577.0
> (timed-prime-test 10007)
10007

...and I gave up waiting after several minutes. We've gone from approximately 1.6 seconds to around 48 seconds each of the first three primes over 1,000!

It's possibly worth noting that one of the footnotes in section 1.2.6 pretty much points out the flaw in using fast-expt:

"The reduction steps in the cases where the exponent e is greater than 1 are based on the fact that, for any integers x, y, and m, we can find the remainder of x times y modulo m by computing separately the remainders of x modulo m and y modulo m, multiplying these, and then taking the remainder of the result modulo m. For instance, in the case where e is even, we compute the remainder of b^e/2 modulo m, square this, and take the remainder modulo m. This technique is useful because it means we can perform our computation without ever having to deal with numbers much larger than m."

The magic phrase being "it means we can perform our computation without ever having to deal with numbers much larger than m". When we don't use this technique we do end up dealing with numbers larger than m. Much larger. The interpreter then ends up using less performant integer representations for most of its calculations and we get the degredation witnessed above.