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.25

From Drewiki
Jump to: navigation, search

Problem

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

(define (expmod base exp m) 
  (remainder (fast-expt base exp) m))

Is she correct? Would this procedure serve as well for our fast prime tester? Explain.

Solution

Alyssa's suggestion is correct: her expmod procedure computes an and then finds its remainder modulo n, per the description in the text of the Fermat test. However, the original expmod procedure is faster than Alyssa's for large prime candidates.

As explained in footnote 1.46 of the text, the original expmod procedure performs "reduction steps" to constrain the computation to numbers not much larger than n, the primality candidate. When the result of a computation exceeds the largest value that can be stored in a machine register, the Scheme implementation must resort to pure software implementations of arithmetic (that is, assuming the Scheme implementation handles arbitrary-precision integer arithmetic at all). The performance of these software-based arithmetic procedures is dependent on the size of the integers (i.e., the performance of the procedures has non-constant order of growth), so the reducation-based expmod given in the text will generally have better performance than Alyssa's method for large n, since an (as computed by Alyssa's expmod procedure) is much larger than numbers near n for large n and a > 1.

For small prime candidate numbers, however, Alyssa's method may be slightly faster than the original expmod procedure, because Alyssa's method performs fewer remainder operations.

Personal tools