PythonでPow(x, n)を実装する方法｜ライブラリ関数を使わずにべき乗を計算するアルゴリズム

問題の概要

2つの入力 x と n が与えられたとします。x は -100.0 から 100.0 の範囲に収まる実数、n は32ビット符号付き整数です。ここでの課題は、ライブラリ関数を使用せずに x の n 乗（x^n）を求めることです。

例えば、入力が x = 12.1、n = -2 の場合、出力は 0.00683 となります。

解法のアプローチ：バイナリ累乗法（繰り返し二乗法）

この問題は「バイナリ累乗法（繰り返し二乗法）」と呼ばれる手法で効率的に解けます。指数を2進数として扱い、計算回数を O(log n) まで削減できるのがポイントです。手順は以下の通りです。

• power に |n|（n の絶対値）を代入し、res を 1.0 で初期化する
• power が 0 になるまで以下を繰り返す
  • power の最下位ビットが 1 なら、res := res × x とする
  • x := x × x とする（x を2乗して更新）
• n が負の場合は 1 / res を返す
• それ以外の場合は res をそのまま返す

仕組みのポイント

各ループで x を2乗しながら、power を右シフト（>>= 1）していくことで、「n を2進数で表したときのビットが立っている位置」に対応する x の累乗だけを掛け合わせることができます。これにより、単純な掛け算の繰り返し（O(n)）よりも大幅に高速な計算が可能になります。また、n が負の場合は最後に逆数を取ることで対応します。

Pythonでの実装例

それでは、実際のコードを見て理解を深めましょう。

class Solution(object):
    def myPow(self, x, n):
        power = abs(n)
        res = 1.0
        while power:
            if power & 1:
                res *= x
            x *= x
            power >>= 1
        if n < 0:
            return 1 / res
        return res

ob1 = Solution()
print(ob1.myPow(45, -2))
print(ob1.myPow(21, 3))

入力

45
-2
21
3

出力

0.0004938271604938272
9261.0

まとめ

この実装では、繰り返し二乗法を用いることで、ライブラリ関数に頼らずに x^n を O(log n) の時間計算量で求めています。負の指数にも対応しており、LeetCode の「Pow(x, n)」問題などでも定番の解法です。ビット演算（& 1 による奇数判定、>>= 1 による右シフト）を活用する点が、このアルゴリズムのエレガントなところと言えるでしょう。