SICP 1.2 exercises cont. 11Posted: January 17, 2013
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.
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.