SICP Exercise 1.26

Question

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 \(\Theta(\log{n})\) process into a \(\Theta(n)\) process.” Explain.

Answer

To understand this, remember that the Scheme interpreter uses applicative-order evaluation. This means that the interpreter first evaluates all the arguments before applying the operation. In this case, this causes the interpreter to evaluate expmod twice for each call to the function This means that with every step, the work to be performed doubles. This is equivalent to an order of growth of \(\Theta(2^n)\). Since the original order of growth was \(\Theta(\log{n})\), the total order of growth now will be \(\Theta(\log{(2^n)})\), which is the same thing as \(\Theta(n)\).