Square-and-multiplyを使った冪乗計算

#数学 

\(N^x\) を計算するとき、単純に計算すると

$$N^x=N\cdot N\cdot N\cdots N$$

と \(x\) 回掛けるので、計算量は \(x\) である。

では、 \(x\) を 2 進数で \(x_{m-1} x_{m-2} \dots x_1 x_0\) と表す（つまり \(x=2^0x_0+2^1x_1+\cdots+2^{m-2}x_{m-2}+2^{m-1}x_{m-1}\)）として、次のように計算すると

$$ \begin{align} N^x&=N^{2^0x_0+2^1x_1+\cdots+2^{m-2}x_{m-2}+2^{m-1}x_{m-1}}\\ &=N^{2^0x_0}\cdot N^{2^1x_1}\cdots N^{2^{m-2}x_{m-2}}\cdot N^{2^{m-1}x_{m-1}} \end{align} $$

と \(m=O(\log_2 x)\) 回の計算量で済みそうである。しかし、それは事前に \(N^{2^i}\) それぞれを計算しておいた場合であり、そうでないなら計算量は変わらない。

Square-and-multiply

では、他に方法はあるのだろうか？その例として、 square-and-multiply という方法がある。これは 2 進数の上の桁から順に

• 0 なら現在の値を 2 乗する（1 ステップ消費）
• 1 なら
  • はじめて 1 が出てきたなら何もしない（0 ステップ消費）
  • 2 回目以降なら 2 乗したうえで、 \(N\) を掛け算する（2 ステップ消費）

というものである。いくつかの例を見ていく：

\(x=3\) (2 進数で \(11\)) なら

$$N^3=(N\to N\to N^2\cdot N=N^3)$$

\(x=10\) (2 進数で \(1010\)) なら

$$N^{10}=(N\to N\to N^2\to (N^2)^2\cdot N=N^5\to (N^5)^2=N^{10})$$

これは \(x=10\) ステップ必要だったのが、 4 ステップに減っている。

では、計算量としてはどうなっているのかを考える。先ほどのリンク先にはその議論はなかったが、 \(x\) の 2 進数がすべて 1 であったとしても、 2 ステップが \(\log_2 x\) 回あるわけなので、結局その計算量は \(O(\log_2 x)\) ということになる。