# sicp-ex-1.25

The modified version of expmod computes huge intermediate results.

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.

For example:

``` (define (square m)
(display "square ")(display m)(newline)
(* m m))

=> (expmod 5 101 101)
square 5
square 24
square 71
square 92
square 1
square 1
5
=> (remainder (fast-expt 5 101) 101)
square 5
square 25
square 625
square 390625
square 152587890625
square 23283064365386962890625
5
```

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.