Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 1.26

From Drewiki
Jump to: navigation, search

Problem

Louis Reasoner is having great difficulty doing exercise 1.24. His fast-prime? test seems to run more slowly than his prime? test. Louis calls his friend Eva Lu Ator over to help. When they examine Louis's code, they find that he has rewritten the expmod procedure to use an explicit multiplication, rather than calling square:

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

"I don't see what difference that could make," says Louis. "I do." says Eva. "By writing the procedure like that, you have transformed the <math>\theta(\log n)</math> process into a <math>\theta(n)</math> process." Explain.

Solution

Eva is correct: by evaluating the expression:

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

the combination (expmod base (/ exp 2) m) is evaluated twice at each step in the computation when the exponent is even, eliminating the benefit of the fast exponentiation algorithm -- which halves the exponent when the exponent is even -- therefore eliminating the feature of the algorithm that makes it <math>\theta(\log n)</math>.

We can illustrate this effect with an example using the substitution method on Louis's expmod procedure:

(define r remainder)
 
(expmod 2 8 8)
 
(r (*
    (expmod 2 4 8)
    (expmod 2 4 8))
   8)
 
(r (*
    (r (*
        (expmod 2 2 8)
        (expmod 2 2 8))
       8)
    (r (*
        (expmod 2 2 8)
        (expmod 2 2 8))
       8))
   8)
 
(r (*
    (r (*
        (r (*
            (expmod 2 1 8)
            (expmod 2 1 8))
           8)
        (r (*
            (expmod 2 1 8)
            (expmod 2 1 8))
           8))
       8)
    (r (*
        (r (*
            (expmod 2 1 8)
            (expmod 2 1 8))
           8)
        (r (*
            (expmod 2 1 8)
            (expmod 2 1 8))
           8))
       8))
   8)
 
(r (*
    (r (*
        (r (*
            (r (* 2
                  (expmod 2 0 8))
               8)
            (r (* 2
                  (expmod 2 0 8))
               8))
           8)
        (r (*
            (r (* 2
                  (expmod 2 0 8))
               8)
            (r (* 2
                  (expmod 2 0 8))
               8))
           8))
       8)
    (r (*
        (r (*
            (r (* 2
                  (expmod 2 0 8))
               8)
            (r (* 2
                  (expmod 2 0 8))
               8))
           8)
        (r (*
            (r (* 2
                  (expmod 2 0 8))
               8)
            (r (* 2
                  (expmod 2 0 8))
               8))
           8))
       8))
   8)
 
(r (*
    (r (*
        (r (*
            (r (* 2
                  1)
               8)
            (r (* 2
                  1)
               8))
           8)
        (r (*
            (r (* 2
                  1)
               8)
            (r (* 2
                  1)
               8))
           8))
       8)
    (r (*
        (r (*
            (r (* 2
                  1)
               8)
            (r (* 2
                  1)
               8))
           8)
        (r (*
            (r (* 2
                  1)
               8)
            (r (* 2
                  1)
               8))
           8))
       8))
   8)

Louis's version of expmod performs 15 remainder operations for an exponent of value 8 (roughly 2n operations).

Personal tools