# SICP - Solution: Exercise 1.26

##### October 19, 2018

## 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 ${\mathrm\Theta(\log n)}$ process into a ${\mathrm\Theta(n)}$ process.” Explain.

## Solution #

Louis Reasoner version of `expmod`

doesn’t user a `square`

function, but use a `*`

. This might not seem a lot, but the interpreter uses **applicative-order evaluation**, meaning it will “evaluate the arguments and then apply”.

In case of `(square (expmod base (/ exp 2) m))`

, the parameter of `square`

will be evaluated once, then `square`

will be applied.

In the case of `(* (expmod base (/ exp 2) m) (expmod base (/ exp 2) m))`

each of the two parameters of `*`

will be fully evaluated before the `*`

will be applied. Since both are recursive call, it will double the work to do, whenever this branch is executed. The complexity becomes $\mathrm\Theta(\log 2^n)=\mathrm\Theta(n \log 2)=\mathrm\Theta(n)$.