**Exercise 1.26:** 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 \( \Theta(\log n) \) process into a \( \Theta(n) \) process.” Explain.

Just like the recursive binary tree computational procedure for Fibonacci numbers was exponential so is this process
exponential because of the double call to expmod. This double call creates a tree of depth log_{2}(n). The
amount of nodes in a tree (the amount of computational steps to perform the algorithm), of depth log_{2}(n)
is \( 2^{\log_2 n} = n \). This means the algorithm is indeed \( \Theta(n) \).