累乗計算の高速化 - へなちょここーだー

HackerRankのAntiPalindromic Stringsを解くときにどうしても累乗計算がO(n)になってしまいタイムアウトになってしまっていたところ、凄くキレイで高速なアルゴリズムを発見！
高速な累乗計算 - あどけない話
これを使ってみました。

単純なxのn乗をmを法として求めるアルゴリズム

long myPow(long x, long n, long m){
  long result = 1;
  for(int i = 0; i < n; i++){
    result *= x;
    result = result % m;
  }
  return result;
}

改善後のアルゴリズム

ここから、累乗計算の方法を改良していきましょう。その例として、 ${3^{19}}$ を計算してみます。

1. まずは19を2進法であらわす。

${\begin{eqnarray} 19 &=& 2^0 + 2^1 + 2^4 \\ &=& 1 + 2 + 16 \end{eqnarray}}$

2. これを利用して累乗を計算する。

${ \begin{eqnarray} 3^{19} &=& 3^{1 + 2 + 16} \\ &=& 3 \cdot 3^2 \cdot 3^{16} \end{eqnarray}}$

3. これを計算できる漸化式を考える。

${x^n = \begin{cases} (x^2)^{n / 2} &\text{if } n \text{ が偶数}\\ x \cdot x^{n - 1} &\text{if } n \text{ が奇数} \end{cases}}$

4. この漸化式による計算を考える。

${ \begin{eqnarray} 3^{19} &=& 3 \cdot 3^{18} \\ &=& 3 \cdot (3^2)^9 \\ &=& 3 \cdot 3^2 \cdot (3^2)^8\\ &=& 3 \cdot 3^2 \cdot (3^4)^4\\ &=& 3 \cdot 3^2 \cdot (3^8)^2\\ &=& 3 \cdot 3^2 \cdot 3^{16} \end{eqnarray}}$

いかがでしょうか。これにmを法にして解くという条件を加えて書いたコードは次の通り。

long myPow(long x, long n, long m){
  if(n == 0)
    return 1;
  if(n % 2 == 0)
    return myPow(x * x % m, n / 2, m);
  else
    return x * myPow(x, n - 1, m) % m;
}

これでO(log n)になり、バッチリ解くことが出来ました。ただ、また新しい記事を発見。
累乗を求めるプログラムの速度計測 - ak毎日ブログ
どうやら再帰関数を使うと関数の呼び出しで遅くなるからfor文を使った方が速いらしい。なるほど、勉強になります。