练习 1.26

原本的 expmod 在每次 exp 为偶数时,可以将计算量减少一半:

(remainder (square (expmod base (/ exp 2) m)) m)

但是因为 Louis 的 expmod 重复计算了两次 (expmod base (/ exp 2) m)

(remainder (* (expmod base (/ exp 2) m)
              (expmod base (/ exp 2) m))
           m)

所以每次当 exp 为偶数时, Louis 的 expmod 过程的计算量就会增加一倍,因此原本 \(\Theta(\log n)\) 的计算过程变成了 \(\Theta(n)\)

讨论

blog comments powered by Disqus