**Exercise 1.25:** 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.

While the procedure is mathematically accurate and would produce the right results, `fast-expt`

would produce enormous
numbers that would then have to be reduced modulo m. For example:

```
(expmod 2 10 7)
(remainder (fast-expt 2 10) 7)
(remainder 1024 7)
```

The 1024 might not seem so bad at first.

```
(remainder (fast-expt 2 10) 7)
(remainder 1267650600228229401496703205376 7)
```

That’s a bit excessive. The version bellow keeps the number in check.

```
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
```

I am taking some liberty here in skipping a few minor steps.

```
(expmod 2 10 7)
(remainder (square (expmod 2 5 7)) 7)
(remainder (square (remainder (* 2 (expmod 2 4 7)) 7)) 7)
(remainder (square (remainder (* 2 (remainder (square (expmod 2 2 7)) 7)) 7)) 7)
(remainder (square (remainder (* 2 (remainder (square (remainder (square (expmod 2 1 7)) 7)) 7) 7) 7)) 7)
(remainder (square (remainder (* 2 (remainder (square (remainder (square (remainder (* 2 1) 7)) 7)) 7)) 7)) 7)
(remainder (square (remainder (* 2 (remainder (square (remainder (square (remainder 2 7)) 7)) 7)) 7)) 7)
(remainder (square (remainder (* 2 (remainder (square (remainder (square 2) 7)) 7)) 7)) 7)
(remainder (square (remainder (* 2 (remainder (square (remainder 4 7)) 7)) 7)) 7)
(remainder (square (remainder (* 2 (remainder (square 4) 7)) 7)) 7)
(remainder (square (remainder (* 2 2) 7)) 7)
(remainder (square (remainder 4 7)) 7)
(remainder (square 4) 7)
2
```

The key difference is that at no point do any of the numbers grow to be much larger than the base.