C++でx^(y^2)とy^(x^2)のどちらが大きいかを判定する方法

問題概要

この問題では、2つの整数 x と y が与えられ、x^(y^2) と y^(x^2) のうち大きい方を求めることが課題となります。

具体例で理解しよう

入力：x = 4、y = 3

出力：3^(4^2)

説明：

• x^(y^2) = 4^(3^2) = 4^9 = 262144
• y^(x^2) = 3^(4^2) = 3^16 = 43046721

基数が小さい方の式が大きくなるという、一見すると直感に反する興味深い結果です。

解法アプローチ

最も素朴な方法は、両方の値を実際に計算してから大きい方を出力することです。しかし、指数が大きくなると結果が爆発的に増大し、標準のデータ型ではオーバーフローを起こしてしまうため、大きな値には使えません。

そこで有効なのが、自然対数（ln）を利用するシンプルなアプローチです。

ln(x^(y^2)) = (y^2) × ln(x)
ln(y^(x^2)) = (x^2) × ln(y)

これらの値は x・y に直接比例しないため、両辺を (x^2) × (y^2) で割ると、次のようにきれいに変形できます。

ln(x^(y^2)) ÷ ((x^2) × (y^2)) = ln(x) / x^2
ln(y^(x^2)) ÷ ((x^2) × (y^2)) = ln(y) / y^2

つまり、ln(x)/x^2 と ln(y)/y^2 の大小を比較すればよいことが分かります。関数 f(t) = ln(t)/t^2 は t ≥ 2 の範囲で単調減少するため、次のシンプルな判定式が成立します。

x > y ならば、x^(y^2) < y^(x^2)

この性質を利用すれば、巨大なべき乗を実際に計算することなく、O(1) の定数時間で大小関係を判定できます。

解法の動作を示すプログラム

サンプルコード

#include <iostream>
using namespace std;

// x^(y^2) が大きければ true を返す
bool checkGreaterVal(int x, int y) {
    if (x > y)
        return false;
    else
        return true;
}

int main() {
    int x = 3;
    int y = 5;
    cout << "The greater value is ";
    if (checkGreaterVal(x, y))
        cout << x << "^(" << y << "^2)";
    else
        cout << y << "^(" << x << "^2)";
    return 0;
}

出力

The greater value is 3^(5^2)

コードの解説

checkGreaterVal 関数は、x と y の大小関係を比較します。x ≤ y の場合は true を返し、x^(y^2) の方が大きいと判定します。逆に x > y の場合は false を返し、y^(x^2) が大きいと判断されます。上記の例では x = 3、y = 5 なので、3^(5^2) = 3^25 が 5^9 よりも大きいことが正しく出力されています。