トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

繰り返し2乗法

[アルゴリズム]

練習のための問題は 競技プログラミングの履歴

要はn ^ 30のような大きなべき乗を高速に計算したい

繰り返し2乗法

  わかりやすいリンク

  詳しい解説

  解説

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
お名前: コメント: