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^{n}), 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.

## 1 comment:

Thanks for the answer, very useful.

Post a Comment