Solution to SICP Exercise 1.25

Structure and Interpretation of Computer Programs

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.

Advertisements