SICP - Solution: Exercise 1.26

Oct 19, 2018 04:03 · 239 words · 2 minute read

Exercise 1.26: 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 ${\mathrm\Theta(\log\;n)}$ process into a ${\mathrm\Theta(n)}$ process.” Explain.

Solution

Louis Reasoner version of expmod doesn’t user a square function, but use a *. This might not seems a lot, but the interpreter uses applicative-order evaluation, meaning it will “evaluate the arguments and then apply”.

In case of (square (expmod base (/ exp 2) m)), the parameter of square will be evaluated once, then square will be applied.

In the case of (* (expmod base (/ exp 2) m) (expmod base (/ exp 2) m)) each of the two parameters of * will be fully evaluated before the * will be applied. Since both are recursive call, it will double the work to do, whenever this branch is executed. The complexity becomes $\mathrm\Theta(\log\;2^n)=\mathrm\Theta(n\;\log\;2)=\mathrm\Theta(n)$.