Louis Reasoner is having great difficulty doing exercise 1.24
test seems to run more slowly than his
test. Louis calls his friend Eva Lu Ator over to help. When they examine Louis's code, they find that he has rewritten the
procedure to use an explicit multiplication, rather than calling
(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 Θ(log n) process into a Θ(n) process.'' Explain.
There are no comments yet.
You must log in to post a comment.Login