Solution to SICP Exercise 1.25

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.