[アルゴリズム]
練習のための問題は 競技プログラミングの履歴
要はn ^ 30のような大きなべき乗を高速に計算したい
繰り返し２乗法
わかりやすいリンク
詳しい解説
- Fast modular exponentiation ... modular exponentiation (= 冪剰余)
解説
5^31, 5^30について考える
- 5は基数で、31は指数と呼ぼう。
- 31はすべて2の累乗した数で構成されているぞ、これは驚き（わざとらしい）
- 30はすべてではないが2の累乗した数で表せる
31 = 16 + 8 + 4 + 2 + 1 = 2^4 + 2^3 + 2^2 + 2^1 + 2^0 30 = 16 + 8 + 4 + 2 + 0 = 2^4 + 2^3 + 2^2 + 2^1
- ということは、31を2進数化してみると全て1が立つはず
- 31は最後のbitだけ0になるな
31 = 16 + 8 + 4 + 2 + 1 = 2^4 + 2^3 + 2^2 + 2^1 + 2^0 = 11111(2) 30 = 16 + 8 + 4 + 2 + 0 = 2^4 + 2^3 + 2^2 + 2^1 + 0 = 11110(2)
指数法則 で、それぞれは個々の累乗に分解できる
5^31 = 5^16 + 5^8 + 5^4 + 5^2 + 5^1 5^30 = 5^16 + 5^8 + 5^4 + 5^2 + 0
- ここからわかるのは、2進数表記で0になっているところは0で、1になっているところは基数^桁数になっているということ
- それを利用すればプログラムが組める
ソースコードに落とし込む
- 参考コード
- 冪剰は英語で "power" なので、関数名は pow などにすることが多い
def pow(x, n)
puts "#{x}^#{n}"
ans = 1
while n > 0
puts "n = #{n}, x = #{x}"
ans = ans * x if n.odd?
x = x * x
n >>= 1
end
ans
end
puts pow(5, 30)
# 5^30
# n = 30, x = 5 (= 5^1)
# n = 15, x = 25 (= 5^2)
# n = 7, x = 625 (= 5^4)
# n = 3, x = 390625 (= 5^8)
# n = 1, x = 152587890625 (= 5^16)
# 931322574615478515625
puts pow(5, 31)
# 5^31
# n = 31, x = 5 (= 5^1) ← この時は足さない
# n = 15, x = 25 (= 5^2)
# n = 7, x = 625 (= 5^4)
# n = 3, x = 390625 (= 5^8)
# n = 1, x = 152587890625 (= 5^16)
# 4656612873077392578125