Ken Dyck's Weblog

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.

Posted by Ken Dyck in Programming

2 Comments »

This entry was posted on Sunday, June 19th, 2005 at 9:15 am and is filed under Programming. You can follow any responses to this entry through the comments RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to “Solution to SICP Exercise 1.25”

Michael Harrison says:

I think you’re right. In the description of expmod, there’s a telling footnote:

The reduction steps in the cases where the exponent e is greater than 1 are based on the fact that, for any integers x, y, and m, we can find the remainder of x times y modulo m by computing separately the remainders of x modulo m and y modulo m, multiplying these, and then taking the remainder of the result modulo m. For instance, in the case where e is even, we compute the remainder of be/2 modulo m, square this, and take the remainder modulo m. This technique is useful because it means we can perform our computation without ever having to deal with numbers much larger than m. (Compare exercise 1.25.)

September 15th, 2007 at 1:49 pm

Jason says:

If your HLL hooks integers into the big number library instead of overflowing them, then the direct method will work – but as you point out it will be very slow. That method pays for lack of cleverness with space and time.

Since:

ab mod m = (a mod m)(b mod m) mod m
(a + b) mod m = ((a mod m) + (b mod m)) mod m

the algorithm can clamp the numbers at every step.
ie- 32 bits ints are good for primes up into the 10^9s.

December 5th, 2010 at 2:15 pm

Solution to SICP Exercise 1.25

2 Responses to “Solution to SICP Exercise 1.25”

Leave a Reply