乐正

Actions speak louder than words.

Sicp-ex1-26

问题

Louis Reasoner在做练习1.24的时候遇到了很大的困难,他的fast-prime?检查看起来运 行的比prime?还慢。Louis请他的朋友Eva Lu Ator过来帮忙。在检查Louis的代码时,两 个人发现了他重写了expmod过程,其中用了一个显示的乘法,而没有调用square

1
2
3
4
5
6
7
8
(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说,“采用这种方式写出该过程时, 你就把一个$\Theta (\log n)$的计算过程变成$\Theta (n)$的了。” 请解释这一问题。

解答

原本的expmod在当exp是偶数的时候可以减少一倍的计算量,所以它的计算过程是$\Theta (\log n)$的。而改写后的expmod因为需要计算两遍(expmod base (/ exp 2) m),计算 量并没有减少。所以其计算过程是$\Theta (n)$的。

draft

« sicp-ex1-25 sicp-ex1-27 »

Comments