why does this sicp algorithm for the exponent of a number modulo another number work?

This is the definition of fast-exp from 1.2.4 that is refered to:

(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))

If we rename things to closer match expmod it looks like this:

(define (expt base exp)
  (cond ((= exp 0) 1)
        ((even? exp)
         (square (expt base (/ exp 2))))
        (else
         (* base (expt base (- exp 1))))))

To get a naive expmod we can, for now, just calculate the remainder of each clause:

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

So far we have not used the footnote (ab) mod m = ((a mod m)(b mod m) mod m). Of course a special case of this is (aa) mod m = ((a mod m)(a mod m) mod m) which gives (remainder (square a) m) = (remainder (sqaure (remainder a m)) m). We can use this with the even clause so that

         (remainder (square (expt base (/ exp 2))) m)

becomes:

         (remainder (square (remainder (expt base (/ exp 2)) m))
                    m)

In the middle of this we have the remainder of an exponent so this is equivalent to:

         (remainder (square (expmod base (/ exp 2) m)) m)

Using the new even clause we have

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

To simplify the odd clause lets use E in place of (expt base (- exp 1)) for now.

By using the defining properties of mod we can say for any number a:

         a = (+ (* (quotient a m) m) (remainder a m))

So it’s also true that:

         E = (+ (* (quotient E m) m) (remainder E m))

substituting this into our odd clause:

         (remainder (* base E) m)

gives:

         (remainder (* base (+ (* (quotient E m) m) (remainder E m))) m)

We can ignore (* (quotient E m) m) because any term containg this is divisible by m and so will evaluate to 0 when doing the outer remainder, so this equivalent to:

         (remainder (* base (remainder E m)) m)

expanding E to it’s orignal value:

         (remainder (* base (remainder (expt base (- exp 1)) m)) m)

once again, in the middle, we have the remainder of an exponent so this becomes:

         (remainder (* base (expmod base (- exp 1) m)) m)

And our expmod is now:

(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))))

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top