Exercise 1.26 · 习题

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

Θ

(

log

⁡

n

) process into a Θ

(

n

) process.”

Explain.

练习 1.26：Louis Reasoner 在做练习 1.24 时遇到了很大的困难。他的 fast-prime? 检验看起来比 prime? 检验运行得更慢。Louis 请他的朋友 Eva Lu Ator 来帮忙。当他们查看 Louis 的代码时，发现他将 expmod 过程改写为使用显式乘法，而不是调用 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))))

"我看不出这有什么区别，"Louis 说。"我看出来了，"Eva 说，"你这样写，把 Θ(log n) 的计算过程变成了 Θ(n) 的计算过程。"请解释。