C++では、標準ライブラリ <cmath> にある std::pow() を使わなくても、プログラム内で累乗を計算できます。
特に 整数の累乗を扱う場合は、自分で実装する方法がよく使われます。
主な理由は次の通りです。
std::pow()は主に 浮動小数点計算を前提とした関数- 戻り値が
double系になることが多い - 大きな整数計算では 丸め誤差の影響を受ける可能性がある
- 整数累乗だけなら より高速なアルゴリズムを実装できる
ここでは、C++で pow() を使わずに累乗を求める代表的な方法を、基本から高速アルゴリズムまで順に解説します。
ループで掛け算を繰り返す方法（基本）
最も単純な方法は、掛け算を繰り返すことです。
数学的に
2^5 = 2 × 2 × 2 × 2 × 2
なので、これをそのままプログラムにします。
#include <iostream>
using namespace std;
long long power(int base, int exponent)
{
long long result = 1;
for(int i = 0; i < exponent; i++)
{
result *= base;
}
return result;
}
int main()
{
cout << power(2,5) << endl; // 32
}
特徴
この方法は次の条件で使用できます。
- 底（base）が整数
- 指数（exponent）が 0以上の整数
計算量は
O(n)
です。
つまり、指数が大きくなるほど計算回数が増えます。
例
2^100000
のような計算では、100000回の掛け算が必要になります。
再帰関数で累乗を計算する方法
ループの代わりに、再帰関数を使って累乗を定義することもできます。
累乗は次の関係式で表せます。
a^n = a × a^(n-1)
これをそのままコードにすると次のようになります。
#include <iostream>
using namespace std;
long long power(int base, int exponent)
{
if(exponent == 0)
return 1;
return base * power(base, exponent - 1);
}
int main()
{
cout << power(2,5) << endl;
}
特徴
計算量はループと同じです。
O(n)
ただし再帰関数は
- 関数呼び出しのオーバーヘッド
- 深い再帰によるスタック消費
があるため、大きな指数ではあまり実用的ではありません。
二分累乗法（Binary Exponentiation）
指数計算を高速化する代表的なアルゴリズムが 二分累乗法です。
これは 指数を半分に分割して計算する方法です。
累乗には次の性質があります。
指数が偶数の場合
a^n = (a^(n/2))^2
指数が奇数の場合
a^n = a × a^(n-1)
この性質を利用すると、計算回数を大幅に減らすことができます。
再帰版の実装
#include <iostream>
using namespace std;
long long power(long long base, long long exponent)
{
if(exponent == 0)
return 1;
long long half = power(base, exponent / 2);
if(exponent % 2 == 0)
return half * half;
else
return base * half * half;
}
int main()
{
cout << power(2,10) << endl;
}
計算量
二分累乗法では計算量が
O(log n)
になります。
つまり、指数が100万でも必要な掛け算回数は 約20回程度です。
ただし、結果の値が long long に収まるとは限らないため、オーバーフローには注意が必要です。
ループ版の二分累乗（実用的）
実務や競技プログラミングでは、再帰よりも ループ版がよく使われます。
理由は次の通りです。
- スタックを使わない
- 実装が簡潔
- 実行速度が安定する
#include <iostream>
using namespace std;
long long power(long long base, long long exponent)
{
long long result = 1;
while(exponent > 0)
{
if(exponent % 2 == 1)
{
result *= base;
}
base *= base;
exponent /= 2;
}
return result;
}
int main()
{
cout << power(2,10) << endl;
}
ビット演算を使った高速累乗
二分累乗法は、ビット演算を使うとさらに簡潔に書けます。
long long power(long long base, long long exponent)
{
long long result = 1;
while(exponent)
{
if(exponent & 1)
result *= base;
base *= base;
exponent >>= 1;
}
return result;
}
ビット演算の意味
exponent & 1
→ 指数が奇数か判定
exponent >>= 1
→ 指数を2で割る
テンプレートで汎用化する方法
型を限定せずに使えるようにするため、テンプレート関数にすることもできます。
template<typename T>
T power(T base, long long exponent)
{
T result = static_cast<T>(1);
while(exponent > 0)
{
if(exponent & 1)
result *= base;
base *= base;
exponent >>= 1;
}
return result;
}
この関数は次のような型で使用できます。
int
long long
double
float
ただし次の条件があります。
- 乗算が定義されている型
1が乗算の単位元になる型- 指数は 0以上の整数
pow() を使わない理由
C++では通常
std::pow(2,10)
のように書くことができます。
しかし整数累乗では、自前実装が使われることも多いです。
主な理由は次の通りです。
浮動小数点計算になる
std::pow() は浮動小数点演算を行うため、戻り値は多くの場合
double
になります。
そのため大きな整数では
丸め誤差
が発生する可能性があります。
整数計算として扱いにくい
整数の累乗を求めたい場合、
long long result = pow(2,10);
のようなコードは
- 型変換
- 誤差
などの問題を起こす可能性があります。
自前の二分累乗の方が高速になることがある
二分累乗法を使えば、整数の累乗を
O(log n)
で計算できます。
整数専用の処理であるため、用途によっては std::pow() より効率的になる場合があります。
実装時の注意点
累乗関数を実装するときには、次の点に注意する必要があります。
オーバーフロー
例えば
2^63
は long long に収まりません。
整数型では、範囲を超えると未定義動作になる可能性があります。
負の指数
整数型では
2^-3 = 1/8
のような値を表現できません。
負の指数を扱う場合は
double
などの型を使う必要があります。
0^0 の扱い
多くのプログラムでは
0^0 = 1
として扱われますが、数学的には文脈によって定義が異なる場合があります。
まとめ
C++で pow() を使わずに累乗を計算する方法には次のようなものがあります。
| 方法 | 計算量 | 特徴 |
|---|---|---|
| ループ | O(n) | 実装が簡単 |
| 再帰 | O(n) | 数学的に理解しやすい |
| 二分累乗（再帰） | O(log n) | 高速 |
| 二分累乗（ループ） | O(log n) | 実用的 |
| ビット演算版 | O(log n) | 最も一般的 |
整数の累乗計算では、特に
二分累乗法（Binary Exponentiation）
が広く使われています。
以上、C++でpow関数を使わないで累乗の計算をする方法についてでした。
最後までお読みいただき、ありがとうございました。
