C++でpow(x, y)をO(log y)の時間計算量で実装する反復関数の書き方

この記事では、2つの整数 x と y が与えられたとき、標準ライブラリの pow(x, y) と同等の結果を返す関数を、反復処理 を用いて O(log y) の時間計算量で実装する方法を解説します。

アルゴリズムの考え方

単純なべき乗計算をループで行うと、y 回の掛け算が必要となり計算量は O(y) になります。しかし、「繰り返し二乗法（バイナリ累乗法）」と呼ばれる手法を使うと、計算量を O(log y) まで削減できます。

基本的なアイデアは次のとおりです。

• 結果を格納する変数 result を 1 で初期化します。
• y が奇数のときだけ、result に x を掛けます。
• 各反復のたびに、y を半分にし（右シフト）、x を 2 乗していきます。

y をビット列として見ると、立っているビットに対応する x の冪だけが最終結果に寄与するため、反復回数は y のビット長、すなわち log₂(y) 回程度で済みます。

入出力例

入力

x = 7 , y = 3

出力

343

7 の 3 乗は 7 × 7 × 7 = 343 です。

C++での実装コード

#include <iostream>
using namespace std;

void calcPower(int x, unsigned int y) {
    int result = 1;
    while (y > 0) {
        // 最下位ビットが1なら（yが奇数なら）結果にxを掛ける
        if (y & 1)
            result *= x;
        y = y >> 1;   // yを半分にする
        x = x * x;    // xを2乗する
    }
    cout << result;
}

int main() {
    int x = 7;
    unsigned int y = 3;
    cout << x << " raised to " << y << " is ";
    calcPower(x, y);
    return 0;
}

実行結果

raised to 3 is 343

処理の流れを追ってみる

x = 7、y = 3 の場合の動作を確認してみましょう。

• 初期状態： result = 1、x = 7、y = 3（2進数で 11）
• 1回目の反復： y & 1 = 1 なので result = 1 × 7 = 7。その後 y = 1、x = 49
• 2回目の反復： y & 1 = 1 なので result = 7 × 49 = 343。その後 y = 0、x = 2401
• ループ終了： result = 343 を出力

このように、わずか 2 回の反復で計算が完了し、y が大きくなるほど O(y) の素朴な実装との差が顕著になります。

まとめ

ビット演算（AND・右シフト）と繰り返し二乗法を組み合わせることで、pow(x, y) 相当の関数を O(log y) の時間計算量で効率的に実装できます。大きな指数を持つべき乗計算が必要な場面で非常に有用なテクニックなので、ぜひ覚えておきましょう。