Exercise 1.25 of SICP

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

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.

(expmod 2 100 7)
(remainder (fast-expt 2 10) 7)
(remainder 1267650600228229401496703205376 7)
That’s a bit excessive.

The version bellow keeps the number in check.

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.

Leave a Reply