Exercise 1.25
Imports: [[Chapter 1.1]] square, [[Chapter 1.2]] fast-expt expmod
(define (fast-expt b n)
(cond ((= n 0) 1)
((even? n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))
(fast-expt 2 5) => 32
(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))))
This procedure works, but it is not as efficient. The Fermat test takes much longer using alyssa-expmod—longer by three orders of magnitude. The key to the original expmod is not only successive squaring (which fast-expt does as well in Alyssa's procedure), but also calling remainder between each squaring. Alyssa's procedure does not, so the value becomes enormous, requiring bignums. Suppose we test primality of \(n = 9\), choosing \(a = 5\). Using the original expmod, the process evolves like so:
(define r remainder)
(define s square)
(expmod 5 9 9)
=> (r (* 5 (expmod 5 8 9)) 9)
=> (r (* 5 (r (s (expmod 5 4 9)) 9)) 9)
=> (r (* 5 (r (s (r (s (expmod 5 2 9)) 9)) 9)) 9)
=> (r (* 5 (r (s (r (s (r (s (expmod 5 1 9)) 9)) 9)) 9)) 9)
=> (r (* 5 (r (s (r (s (r (s (r (* 5 (expmod 5 0 9)) 9)) 9)) 9)) 9)) 9)
=> (r (* 5 (r (s (r (s (r (s (r (* 5 1) 9)) 9)) 9)) 9)) 9)
=> (r (* 5 (r (s (r (s (r (s (r 5 9)) 9)) 9)) 9)) 9)
=> (r (* 5 (r (s (r (s (r (s 5) 9)) 9)) 9)) 9)
=> (r (* 5 (r (s (r (s (r 25 9)) 9)) 9)) 9)
=> (r (* 5 (r (s (r (s 7) 9)) 9)) 9)
=> (r (* 5 (r (s (r 49 9)) 9)) 9)
=> (r (* 5 (r (s 4) 9)) 9)
=> (r (* 5 (r 16 9)) 9)
=> (r (* 5 7) 9)
=> (r 35 9)
=> 8
Compare this to the evolution of the process using Alyssa's procedure:
The original expmod doesn't need to deal with numbers anywhere near that size. This number may seem okay, but it will grow exponentially with \(n\) by definition, and will quickly require arbitrary precision arithmetic, which is much slower than fixnum arithmetic.