Python で繰り返し2乗法を書いてみた

繰り返し2乗法とは指数を2の累乗の積に分解して計算を効率化するテクニック。計算量が Olog(N) になる。

ただし Python の場合は組み込みの関数として pow が実装されているが勉強のため書いてみた。

// 3 の 50 乗の計算
x = 3
n = 50

def pow(x, n):
    ans = 1
    // n が 0 になるまで計算を続ける
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

print(pow(3, 50))

繰り返し2乗法は N 個のものそれぞれを選ぶ選ばないなどの選択をするときに 2^N となるのでこのような場合に使用する。