## **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.26

## Problem

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 <math>\theta(\log n)</math> process into a <math>\theta(n)</math> process." Explain.

## Solution

Eva is correct: by evaluating the expression:

(remainder (* (expmod base (/ exp 2) m) (expmod base (/ exp 2 m)) m))

the combination `(expmod base (/ exp 2) m)` is evaluated twice at each
step in the computation when the exponent is even, eliminating
the benefit of the fast exponentiation algorithm -- which halves the
exponent when the exponent is even -- therefore eliminating the feature of the algorithm that makes it <math>\theta(\log n)</math>.

We can illustrate this effect with an example using the substitution
method on Louis's `expmod` procedure:

(define r remainder) (expmod 2 8 8) (r (* (expmod 2 4 8) (expmod 2 4 8)) 8) (r (* (r (* (expmod 2 2 8) (expmod 2 2 8)) 8) (r (* (expmod 2 2 8) (expmod 2 2 8)) 8)) 8) (r (* (r (* (r (* (expmod 2 1 8) (expmod 2 1 8)) 8) (r (* (expmod 2 1 8) (expmod 2 1 8)) 8)) 8) (r (* (r (* (expmod 2 1 8) (expmod 2 1 8)) 8) (r (* (expmod 2 1 8) (expmod 2 1 8)) 8)) 8)) 8) (r (* (r (* (r (* (r (* 2 (expmod 2 0 8)) 8) (r (* 2 (expmod 2 0 8)) 8)) 8) (r (* (r (* 2 (expmod 2 0 8)) 8) (r (* 2 (expmod 2 0 8)) 8)) 8)) 8) (r (* (r (* (r (* 2 (expmod 2 0 8)) 8) (r (* 2 (expmod 2 0 8)) 8)) 8) (r (* (r (* 2 (expmod 2 0 8)) 8) (r (* 2 (expmod 2 0 8)) 8)) 8)) 8)) 8) (r (* (r (* (r (* (r (* 2 1) 8) (r (* 2 1) 8)) 8) (r (* (r (* 2 1) 8) (r (* 2 1) 8)) 8)) 8) (r (* (r (* (r (* 2 1) 8) (r (* 2 1) 8)) 8) (r (* (r (* 2 1) 8) (r (* 2 1) 8)) 8)) 8)) 8)

Louis's version of `expmod` performs 15 `remainder` operations for an
exponent of value 8 (roughly 2*n* operations).