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.