<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Exponentiation - 求冪運算 -------- #### 問題 求整數$$ x^n $$的最低$$ m $$位數字。 #### 解法 循環的進行$$ x \times x \times \cdots \times x $$共$$ n $$次乘法，然后截取最低$$ m $$位數字，該算法的時間復雜度為$$ O(n) $$。顯然太慢了。 快速求冪算法如下： $$ x^n = \begin{cases} 1 & n = 0 x & n = 1 x \times (x^2)^{\frac{n-1}{2}} & x is odd (x^2)^{\frac{n}{2}} & x is even \end{cases} $$ 因為次方運算會使$$ x $$迅速增大，導致內置變量$$ int32, int64 $$溢出，因此需要每次計算后對$$ m $$取模。 快速求冪算法的時間復雜度為$$ O(log_2 n) $$。 -------- #### Wikipedia Exponentiation by squaring * 2k-ary算法 * Sliding-Window算法(滑動窗口算法) * Montgomery's ladder技術(M的階梯算法) -------- #### 源碼 [Exponentiation.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Calculation/Exponentiation.h) [Exponentiation.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Calculation/Exponentiation.cpp) #### 測試 [ExponentiationTest.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Calculation/ExponentiationTest.cpp)