原本的 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)\) 。