C++で累乗を計算する方法：std::powの使い方と整数・高速化の実装

C++を用いて数値計算やアルゴリズムの実装を行う際、頻繁に登場するのが累乗（べき乗）の計算です。

C++には標準ライブラリとして提供されている便利な関数から、競技プログラミングや大規模計算で求められる高速な独自実装まで、用途に応じた複数の選択肢が存在します。

単純な計算であれば標準関数で十分ですが、整数の精度を保ちたい場合や、非常に大きな指数の計算を高速化したい場合には、アルゴリズムの理解が欠かせません。

本記事では、C++で累乗を計算するための基本的な手法から、誤差を回避するテクニック、そして繰り返し二乗法を用いた効率的な実装までを詳しく解説します。

std::pow関数の基本と使い方

C++で最も一般的に累乗を計算する方法は、標準ライブラリの <cmath> ヘッダに含まれる std::pow 関数を使用することです。

この関数は、浮動小数点数を用いた計算を前提として設計されています。

std::powの構文と戻り値

std::pow は、第一引数に底 (base)、第二引数に指数 (exponent) を取ります。

C++11以降では、引数の型に応じてオーバーロードが用意されています。

基本的な使い方は以下の通りです。

#include <iostream>
#include <cmath> // std::powを使用するために必要

int main() {
    double base = 2.0;
    double exponent = 3.0;

    // 2の3乗を計算
    double result = std::pow(base, exponent);

    std::cout << base << " の " << exponent << " 乗は " << result << " です。" << std::endl;

    return 0;
}

2 の 3 乗は 8 です。

浮動小数点数による誤差の注意点

std::pow を使用する際に最も注意しなければならないのが、浮動小数点数特有の精度誤差です。

この関数は内部的に対数関数や指数関数を用いて計算されることが多く、整数同士の計算であっても戻り値が微小にズレることがあります。

例えば、std::pow(5, 2) の結果が内部的に 24.99999999999999 のような値になる可能性を否定できません。

これをそのまま整数型 (int) にキャストしてしまうと、小数点以下が切り捨てられ、結果が 24 になってしまうという致命的なバグを引き起こします。

整数での累乗計算と精度の確保

整数同士の累乗計算を正確に行いたい場合、std::pow をそのまま使うのは危険です。

ここでは、整数計算における安全な方法を紹介します。

四捨五入による補正

std::pow の結果を整数に格納する場合は、std::round を用いて四捨五入を行うことで、微小な誤差による切り捨てを防ぐことができます。

#include <iostream>
#include <cmath>

int main() {
    int base = 5;
    int exp = 2;

    // std::roundを使用して誤差を補正しつつintに変換
    int result = static_cast<int>(std::round(std::pow(base, exp)));

    std::cout << "5の2乗 (整数): " << result << std::endl;
    return 0;
}

5の2乗 (整数): 25

ただし、この方法はあくまで小さな数値の場合に有効です。

値が非常に大きくなり、double 型の有効桁数を超えてしまうと、四捨五入以前に情報が欠落するため、正しい整数値を維持できなくなります。

ループを用いた単純な整数累乗

精度の問題を完全に回避するには、自前でループを回して掛け算を行うのが確実です。

#include <iostream>

// 整数用の累乗関数 (単純なループ)
long long integer_pow(long long base, int exp) {
    long long res = 1;
    for (int i = 0; i < exp; ++i) {
        res *= base;
    }
    return res;
}

int main() {
    std::cout << "3の10乗: " << integer_pow(3, 10) << std::endl;
    return 0;
}

この方法は計算量が O(n) （nは指数）となるため、指数が小さい場合には適していますが、指数が数百万、数千万といった巨大な数値になる場合には非常に低速です。

高速な累乗計算：繰り返し二乗法 (Binary Exponentiation)

アルゴリズムの実装において、累乗の計算を高速化する手法として知られているのが繰り返し二乗法（べき乗法）です。

この手法を用いると、計算量を O(log n) にまで削減することができます。

原理の解説

繰り返し二乗法は、以下の数学的性質を利用しています。

• $x^n = (x^2)^{n/2}$ （nが偶数の場合）
• $x^n = x \cdot x^{n-1}$ （nが奇数の場合）

例えば、$2^{10}$ を計算する場合、素朴な方法では10回の掛け算が必要ですが、繰り返し二乗法では以下のように進みます。

1. $2^{10} = (2^2)^5 = 4^5$
2. $4^5 = 4 \cdot 4^4 = 4 \cdot (4^2)^2 = 4 \cdot 16^2$
3. $16^2 = 256$
4. $4 \cdot 256 = 1024$

このように、指数を半分にしながら計算を進めることで、劇的にステップ数を減らすことが可能です。

繰り返し二乗法の実装（再帰・反復）

以下に、再帰を用いた実装と、よりメモリ効率の良い反復（ループ）を用いた実装を示します。

反復（ループ）による実装

#include <iostream>

// 繰り返し二乗法 (反復版)
long long fast_pow(long long base, long long exp) {
    long long res = 1;
    while (exp > 0) {
        // 指数が奇数の場合、現在のbaseを結果に掛ける
        if (exp % 2 == 1) {
            res *= base;
        }
        // baseを二乗し、指数を半分にする
        base *= base;
        exp /= 2;
    }
    return res;
}

int main() {
    long long b = 2;
    long long e = 60; // 大きな指数
    std::cout << b << " の " << e << " 乗は " << fast_pow(b, e) << " です。" << std::endl;
    return 0;
}

2 の 60 乗は 1152921504606846976 です。

この実装では、ビット演算を用いて exp % 2 == 1 を exp & 1、exp /= 2 を exp >>= 1 と書くことも一般的です。

競技プログラミングで必須の「累乗余」

非常に大きな累乗（例：$10^{100000}$）を計算する場合、標準的な整数型（long long など）の最大値を優に超えてオーバーフローしてしまいます。

そのため、多くのアルゴリズム問題では「結果を $10^9 + 7$ で割った余りを求めよ」といった制約が課されます。

これを効率的に計算するのが累乗余 (Modular Exponentiation)です。

累乗余の実装

計算の各ステップで余り（mod）を取ることで、数値が型の上限を超えないように制御します。

#include <iostream>

// 繰り返し二乗法を用いた累乗余の計算
// (base^exp) % mod を計算する
long long mod_pow(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod; // 最初に応答範囲内に収める
    while (exp > 0) {
        if (exp & 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

int main() {
    long long base = 2;
    long long exp = 1000000000;
    long long mod = 1000000007;

    std::cout << "2^10^9 mod (10^9+7) = " << mod_pow(base, exp, mod) << std::endl;
    return 0;
}

2^10^9 mod (10^9+7) = 140625001

注意点： base * base の計算時に一時的に値が大きくなるため、mod が $2 \cdot 10^9$ 程度であれば long long で足りますが、それ以上の場合は型に注意が必要です。

テンプレートとconstexprを用いたコンパイル時計算

C++の強力な機能の一つに、メタプログラミングがあります。

指数が定数として決まっている場合、コンパイル時に累乗を計算しておくことで、実行時の負荷をゼロにすることができます。

constexprによる定数式累乗

C++11以降、constexpr 修飾子を関数に付与することで、コンパイル時に計算可能な関数を定義できます。

#include <iostream>

// コンパイル時にも実行時にも使える累乗関数
constexpr long long static_pow(long long base, int exp) {
    long long res = 1;
    for (int i = 0; i < exp; ++i) {
        res *= base;
    }
    return res;
}

int main() {
    // コンパイル時に計算される
    constexpr long long val = static_pow(3, 4);
    
    std::cout << "3の4乗 (コンパイル時確定): " << val << std::endl;
    return 0;
}

C++14以降では、constexpr 関数内でループや変数宣言が柔軟に行えるようになったため、前述の繰り返し二乗法を constexpr 化することも容易です。

累乗計算における手法の選択基準

C++で累乗を計算する際、どの手法を選ぶべきかは用途によって異なります。

以下の表を参考に最適な方法を選択してください。

まとめ

C++における累乗計算は、単純に見えて奥が深いテーマです。

標準ライブラリの std::pow は非常に便利ですが、浮動小数点数ゆえの誤差という落とし穴があります。

特に整数値を扱う場合には、安易にキャストせず、四捨五入や自前の整数累乗関数を検討することが重要です。

また、パフォーマンスが要求される場面では、繰り返し二乗法が極めて強力な武器となります。

計算量を線形時間から対数時間に短縮するこのアルゴリズムは、効率的なプログラミングを行う上での基礎知識と言えます。

さらに、C++のモダンな機能である constexpr を活用すれば、実行時のパフォーマンスを一切犠牲にすることなく計算を行うことも可能です。

状況に応じて適切な手法を使い分け、正確で高速な数値計算プログラムを構築しましょう。