SICP Exercise 1.26: A Broken expmod

Louis Reasoner is having great difficulty doing exercise 1.24. His fast-prime? test seems to run more slowly than his prime? test. Louis calls his friend Eva Lu Ator over to help. When they examine Louis's code, they find that he has rewritten the expmod procedure to use an explicit multiplication, rather than calling square:

(define (expmod base exp m)
  (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))))

"I don't see what difference that could make," says Louis. "I do." says Eva. "By writing the procedure like that, you have transformed the Θ(log n) process into a Θ(n) process." Explain.

The technique of using successive squaring (introduced in section 1.2.4) to reduce an Θ(n) process to a Θ(log n) process is designed to reduce the number of calculations performed. This technique is applied in expmod so that it calculates (expmod base (/ exp 2) m) only once and then squares the result. The equivalent (Θ(n)) approach would be to calculate (expmod base (- exp 1) m) in each recursive call, regardless of whether exp was even or not.

The change made by Louis causes the process to calculate (expmod base (/ exp 2) m) twice instead of once for each invocation of (expmod base exp m), and then multiplies the results together. Note that I said "for each invocation of (expmod base exp m)" quite deliberately here...

In Louis' version, in order to calculate (expmod base exp m) the interpreter has to first calculate (expmod base (/ exp 2) m) twice. However, for each calculation of (expmod base (/ exp 2) m) the interpreter first has to calculate (expmod base (/ exp 4) m) twice, making four calculations of (expmod base (/ exp 4) m), and so on. The recursion is still log n deep, but the number of calculations at level i in the recursion is 2ⁱ. Here's how the number of calls to expmod pan out for the different processes:

exp	Θ(log n) Process	Θ(n) Process	Louis' Process
0	1	1	1
1	2	2	3
2	3	3	7
4	4	5	15
8	5	9	31
16	6	17	63
32	7	33	127

So we can see that the Θ(log n) process takes log₂n steps, and the Θ(n) process takes n + 1 steps. What about Louis' process? Well, that takes 4n - 1 steps, which is Θ(n). Note that the original prime? test is Θ(√n), so Louis is right - his fast-prime? test does run more slowly than his prime? test.