べき乗

2022-09-24 · algorithms, python

Pythonで再帰を用いて効率的なべき乗関数を実装してみます。
元となるコードは『アルゴリズムサイエンス：入口からの超入門』（著：浅野哲夫）のP.70より引用しました。

コード

下記のコードを使用すると、効率的にべき乗を計算することができます。
例えば、x^13 を計算する場合、実行回数は4回となります。

def power(x, k):
    if k == 1:
        return x
    m = k // 2  # 切り捨て
    t = power(x, m)  # 再帰的に計算
    if k % 2 == 0:
        return t * t
    else:
        return t * t * x

実際の処理の流れ

上記のコードを実行すると、以下のような処理の流れになります。

power(x,13) -> power(x,6) -> power(x,3) -> power(x,1)

• x^13 は x^6 * x と同等
• x^6 は x^3 * x^3 と同等
• x^3 は x^1 * x * x と同等
• x^1 は x と同等