SICP 1.2 exercises cont. 11


I arbitrarily run using the smallish values to show the difference.

(define (expmod base exp m)
  (remainder (fast-expt base exp) m))
10007 *** 64
10009 *** 63
10037 *** 63

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
         (remainder (* base (expmod base (- exp 1) m))

10007 *** 7
10009 *** 7
10037 *** 7

Evidently the simpler procedure is not as good – for even bigger numbers such as the ones tried in previous exercises it takes far longer, suggesting an exponential time relative to n.

I was stumped and impatient so I found the answer which explains this difference nicely.

Comments: I’m not sure if looking at the answer was a good idea or not in this case. I think I would have lagged forever if I hadn’t because I had not even considered the complications caused by large numbers.


expmod needs to be evaluated twice within each recursive call to expmod. This negates the benefit from halving the number of steps for each evaluation of expmod.

Comments: Putting this into words is difficult. I knew what was going on, but couldn’t express it. A good explanation can once again be outsourced here.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s