## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 1.25

## Problem

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.

## Solution

Alyssa's suggestion is correct: her `expmod` procedure computes *a*^{n} and
then finds its remainder modulo *n*, per the description in the text
of the Fermat test. However, the original `expmod` procedure is
faster than Alyssa's for large prime candidates.

As explained in footnote 1.46 of the text, the original `expmod` procedure
performs "reduction steps" to constrain the computation to numbers
not much larger than *n*, the primality candidate. When the result of
a computation exceeds the largest value that can be stored in a
machine register, the Scheme implementation must resort to pure
software implementations of arithmetic (that is, assuming the Scheme
implementation handles arbitrary-precision integer arithmetic at
all). The performance of these software-based arithmetic procedures
is dependent on the size of the integers (i.e., the performance of
the procedures has non-constant order of growth), so the
reducation-based `expmod` given in the text will generally have better
performance than Alyssa's method for large *n*, since *a*^{n} (as computed
by Alyssa's `expmod` procedure) is much larger than numbers near *n* for
large *n* and *a* > 1.

For small prime candidate numbers, however, Alyssa's method may be slightly faster than the original expmod procedure, because Alyssa's method performs fewer remainder operations.