Solution to Exercise 1.25:
Both the original and Alyssa’s version of
expmod give the same result, but Alyssa’s version has much poorer performance. Here is a table comparing times spent (in milliseconds) calculating
fast-prime? with the two different versions:
Times for Alyssa’s version are much higher than those for the original. Why is that?
As I couldn’t figure out how to get DrScheme’s profiler to measure time spent in built-in procedures such as
*, I have to guess where the inefficiency is.
expmod calculates its result incrementally, calling
remainder many times on relatively small values. Alyssa’s
expmod, on the other hand, builds up a huge intermediate value, which is then passed to
remainder once. My guess: because the numbers have grown so large in Alyssa’s version, the built-in operations,
/ are consuming much more time than they do in the original.
Moral of the story: arbitrary precision arithmetic can be expensive.