# SICP 1.2 exercises cont. 11

**Posted:**January 17, 2013

**Filed under:**Improving, SICP Leave a comment

**1.25**

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)) m)) (else (remainder (* base (expmod base (- exp 1) m)) 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.

**1.26**

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.