べき乗

与えられた実数 \(a\) と正の整数 \(n\) について、\(a^{n}\) を計算する問題を考えましょう。標準的でナイーブな実装は単純な for ループを使うものです。\(n - 1\) 回の \(a\) による乗算が行われます:

入力パラメータ \(a\) は整数でも、有理数でも、浮動小数点数でも構いません。さらに言えば、乗算の方法さえ分かっていれば数でなくても構いません。例えば同じアルゴリズムを使って底が有限のモジュロ演算 (暗号アルゴリズムでよく使われる演算) や、行列積 (再帰方程式の評価やグラフの最短路の計算に使われる演算) に関するべき乗を計算できます。何を掛けているのかわからないので、乗算の実行時間は分かりません。そのため実行時間の解析は乗算の数を基準にして行います。

このアルゴリズムよりもずっと速い分割統治アルゴリズムがあります。一番古い記録では紀元前二世紀にインド人韻律学者 Piṅgala (ピンガラ) によって発見されているアルゴリズムで、次の単純な再帰的関係を使うものです: \[ \displaystyle a^{n} = \begin{cases} 1 & \text{if } n = 0 \\ (a^{n/2})^{2} & \text{if } n > 0 \text{ かつ } n \text{ が偶数} \\ (a^{\lfloor n/2 \rfloor})^2 \cdot a & \text{それ以外} \\ \end{cases} \]

このアルゴリズムにおける乗算演算の回数 \(T(n)\) は再帰方程式 \(T(n) \leq T(n/2) + 2\) を満たし、再帰木の方法を使えば解 \(T(n) = O(\log n)\) が分かります。

ほとんど同一のべき乗アルゴリズムを前章で触れたエジプト人農民の掛け算アルゴリズムから導くこともできます。足し算を掛け算に (つまり duplation を squaring (二乗すること) に) 置き換えれば次のようになります: \[ a^{n} = \begin{cases} 1 & \text{if } n = 0 \\ (a^{2})^{n/2} & \text{if } n > 0 \text{ かつ } n \text{ が偶数} \\ (a^{2})^{\lfloor n/2 \rfloor} \cdot a & \text{それ以外} \\ \end{cases} \]

このアルゴリズム ――"squareing and mediation" という名前が相応しいかもしれません―― が行う乗算は \(O(\log n)\) 回だけです。これら二つのアルゴリズムはどちらも漸近的に最良です。なぜなら指数部分は乗算ごとに最大でも二倍にしかならないので、\(a^{n}\) を計算するどんなアルゴリズムも \(\Omega(\log n)\) 回の乗算が必要になるからです。

さらに言うと、\(n\) が 2 のべきのとき、これらのアルゴリズムは \(\log_{2} n\) 回の乗算を行う最良のアルゴリズムそのものになります。しかし他の \(n\) の値では少しだけ速い方法が存在します。例えば \(\textsc{PiṅgalaPower}\) と \(\textsc{PeasantPower}\) は \(a^{15}\) を計算するのに乗算を 6 回行いますが、最良の場合 5 回で済ますことができます: \[ \begin{aligned} \textsc{Piṅgala}: & \quad a \rightarrow a^{2} \rightarrow a^{3} \rightarrow a^{6} \rightarrow a^{7} \rightarrow a^{14} \rightarrow a^{15} \\ \textsc{Peasant}: & \quad a \rightarrow a^{2} \rightarrow a^{4} \rightarrow a^{8} \rightarrow a^{12} \rightarrow a^{14} \rightarrow a^{15} \\ \text{最良 }: & \quad a \rightarrow a^{2} \rightarrow a^{3} \rightarrow a^{5} \rightarrow a^{10} \rightarrow a^{15} \end{aligned} \] 任意の \(n\) について \(n\) 乗を計算するために必要な最小の乗算回数を効率良く計算する問題は長い間未解決です。