[leetcode] 50. Pow(x, n)の「二分累乗法の効率化」はなぜ速いのか

const myPow = function(x, n) {
    function binaryExp(x, n){

        if(n === 0) return 1;
        if(n < 0) return 1 / binaryExp(x, -1 * n);

        if(n % 2 === 1){
            return x * binaryExp(x * x, (n - 1) / 2);
        } else {
            return binaryExp(x * x, n / 2);
        }
    }
    return binaryExp(x, n)
};

このmyPow関数は、数値xをn乗した結果を効率的に計算するためのものです。これは「二分累乗法」という手法を使っています。

基本ケース:

nが0の場合、どんな数でも0乗は1なので、1を返します。

nが負の場合、1 / binaryExp(x, -n)で計算します。これは正の指数で計算して、その結果を逆数にするためです。

再帰的な計算:

nが奇数なら、x binaryExp(x x, (n - 1) / 2)で計算します。xを一度掛けてから、nを半分にします。
nが偶数なら、binaryExp(x * x, n / 2)で計算します。nを半分にして計算を続けます。
例:
myPow(2, 10)の場合、結果は1024になります。このように、指数が大きくても高速に計算できます。

nが負の場合、1 / binaryExp(x, -n)で計算します。これは正の指数で計算して、その結果を逆数にするため？

nが負の場合、例えばx^-3のようなケースを考えてみましょう。

例としてmyPow(2, -3)を考えると：

計算手順:

nが負なので、nを正にして計算します。この場合、n = -3が正の3に変わります。
まず、2^3を計算します。2^3 = 8ですね。
次に、その結果を逆数にします。1 / 8 = 0.125になります。
つまり、2^-3という計算は、「まず2を正の指数で計算し、その結果を逆数にする」という流れで行われます。

なぜこうするのか？

負の指数は数学的に「逆数を取る」という意味を持ちます。x^-nは1 / x^nと同じです。例えば2^-3は、1 / 2^3、すなわち1 / 8です。

このように、まず正の指数で普通に計算してから、その結果の逆数を取ることで、負の指数も正しく計算できます。

なぜこの関数が速いのか

このmyPow関数が速い理由は、「二分累乗法」（Exponentiation by Squaring）を使っているからです。この方法では、計算の回数を大幅に減らすことができます。

通常の計算方法との違い

通常、x^nを計算するには、xをn回掛け算します。例えば、2^10を計算する場合、2 2 2 ... 2を10回行います。これは大きな指数では非常に多くの掛け算が必要になります。

二分累乗法の効率化
二分累乗法では、以下のように計算を分割して進めます：

nが偶数の場合：x^n = (x^2)^(n/2)

nが奇数の場合：x^n = x * (x^2)^((n-1)/2)

この方法では、毎回指数を半分にして計算するため、掛け算の回数が大幅に減ります。

具体例：2^10の場合

2^10は偶数なので、(2^2)^5、つまり4^5に変換します。
4^5は奇数なので、4 (4^2)^2に変換し、次に16^2を計算します。
最終的に16^2 = 256なので、4 256 = 1024という結果が得られます。
これにより、10回の掛け算をする代わりに、わずか4回の掛け算で済むようになります。指数が大きくなるほど、この効率の差はさらに大きくなります。