冪乗-繰り返し二乗法の計算
概要
- 冪乗を高速に計算するアルゴリズム
- 例えば \(7^{50}\)を計算する際に、\(50 = 2^5 + 2^4 + 2^1\)と表現できることを利用して、\(O(logN)\)に計算量を下げることができる
具体例
def pow(x, n):
# 負の乗数の場合は
# xの逆数を取り、nを正の値にする
if n < 0:
x = 1 / x
n = -n
ret = 1
while n:
if n & 1 == 1:
ret *= x
x = x**2
n = n >> 1
return ret
assert pow(2, 10) == 1024
assert pow(2, -2) == 0.25