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:
| Prime number | Original | Alyssa’s |
|---|---|---|
| 1009 | 608 | 2937 |
| 1013 | 578 | 3094 |
| 1019 | 687 | 2877 |
| 10007 | 874 | 93900 |
| 10009 | 875 | 92301 |
| 10037 | 749 | 94035 |
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 remainder and *, I have to guess where the inefficiency is.
The original 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, remainder, *, and / are consuming much more time than they do in the original.
Moral of the story: arbitrary precision arithmetic can be expensive.
Ken Dyck 