SICP Exercise 1.26: Explicit multiplication vs. squaring

From SICP section 1.2.6 Example: Testing for Primality

Exercise 1.26 asks us to consider yet another variation on the fast-prime? procedure from exercise 1.24. This time the expmod procedure has been modified to use an explicit multiplication instead of 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))))

This change causes fast-prime? to run more slowly than the original prime? test by transforming the O(log n) process into a O(n) process. We're asked to explain this transformation.

A cursory inspection of the code makes it seem like the explicit multiplication will cause twice as many calls to expmod because each input argument to * will be evaluated separately, instead of only once when expmod is passed as the single argument to square. This isn't enough to account for the reported slow down.

Let's take a closer look at the process generated by each version of expmod. (Since the only difference between the two versions of expmod is in the branch where exp is even, I'm using powers of 2 for that argument to better illustrate the difference in the resulting processes. I should point out that this is a worst case scenario.)

Here is what the process generated by the original expmod procedure using square might look like:

(expmod 2 8 2)
   (expmod 2 4 2)
       (expmod 2 2 2)
           (expmod 2 1 2)
               (expmod 2 0 2)
               1
           0
       0
   0
0

This is a pretty straightforward linear recursive process. Now let's look at the process for expmod when explicit multiplication is used. (This is only part of the process diagram, but it's enough to see what's going on.)


Right away, it's easy to see what went wrong here. By replacing the call to square with explicit multiplication, we've transformed expmod from a linear recursive process (like the factorial example) into a tree recursion (like the original Fibonacci example). This causes the number of recursive calls to expmod to grow exponentially instead of simply doubling. What was once a O(log n) process is now O(log 2ⁿ), which simplifies to O(n).


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.