sicp-ex-1.25

Scheme is able to handle arbitrary-precision arithmetic, but arithmetic with arbitrarily long numbers is computationally expensive. This means that we get the same (correct) results, but it takes considerably longer.

The remainder operation inside the original expmod implementation, keeps the numbers being squared less than the number tested for primality m. fast-expt however squares huge numbers of a^m size.

tiendo1011

I wrote some procedures for us to help testing the speed:

 ; Helper procedures 
 (define (fast-expt b n) 
   (cond ((= n 0) 1) 
         ((even? n) (square (fast-expt b (/ n 2)))) 
         (else (* b (fast-expt b (- n 1)))))) 
 (define (square x) (* x x)) 
 (define (report-elapsed-time start-time) 
   (display " *** ") 
   (display (- (runtime) start-time))) 
  
 ; The original & modified procedures 
 (define (expmod base exp m) 
   (cond ((= exp 0) 1) 
         ((even? exp) 
           (remainder 
             (square (expmod base (/ exp 2) m)) ; (1) 
             m)) 
         (else 
           (remainder 
             (* base (expmod base (- exp 1) m)) 
             m)))) 
  
 (define (modified-expmod base exp m) 
   (remainder (fast-expt base exp) m)) 
  
 ; Test the speed 
 (define start-time (runtime)) 
 (expmod 999999 1000000 1000000) 
 (report-elapsed-time start-time) 
  
 (define start-time (runtime)) 
 (modified-expmod 999999 1000000 1000000) 
 (report-elapsed-time start-time)

For the original implementation, the elapsed time taken is 543, while the modified version takes 1001921, which is significantly larger. The result maybe different on your machine, but I guess the ratio is somewhat similar.