C++でpow(x, n)を計算するプログラムの作成方法

問題の概要

この記事では、2つの整数 x と n が与えられたときに、pow(x, n)（xのn乗）を計算するC++プログラムの作成方法を解説します。

まず、具体例で問題を確認しましょう。

入力例

x = 5 , n = 3

出力例

125

それでは、pow(x, n) を計算するプログラムを見ていきましょう。

C++での実装例

#include <iostream>
using namespace std;
float myPow(float x, int y) {
    if(y == 0)
        return 1;
    float temp = myPow(x, y / 2);
    if (y % 2 == 0)
        return temp * temp;
    else {
        if(y > 0)
            return x * temp * temp;
        else
            return (temp * temp) / x;
    }
}
int main() {
    float x = 5;
    int n = 7;
    cout << x << " の " << n << " 乗は " << myPow(x, n);
    return 0;
}

出力

5 の 7 乗は 78125

アルゴリズムのポイント：繰り返し二乗法

このプログラムは「繰り返し二乗法（バイナリ累乗法）」と呼ばれる効率的なアプローチを採用しています。指数を半分ずつに分割して計算し、その結果同士を掛け合わせることで、少ない計算回数で累乗を求められます。さらに、負の指数の場合も適切に処理している点が特徴です。

処理の流れは以下の通りです。

• ベースケース： 指数が0のときは1を返します（x⁰ = 1）。
• 再帰による分割： myPow(x, y / 2) を再帰的に呼び出し、半分の指数に対する結果を取得します。
• 結果の統合： 指数が偶数なら temp × temp を、奇数なら x × temp × temp を返します。
• 負の指数への対応： 指数が負の場合は (temp × temp) ÷ x を返すことで、正しい値を計算します。

xをn回掛ける単純なループ方式ではO(n)の計算量が必要ですが、この手法ならO(log n)の時間計算量で済みます。そのため、非常に大きな指数を扱う場合でも高速に動作するのが大きなメリットです。