繰り返し二乗法【競技プログラミング】

はじめに

• 今日は疲れているから、あまり時間をかけたくないけど、1個くらい投稿したかったので、簡単だけどswiftで対応していないべき乗計算の関数pow(a,n) = (a^n)を作ることとする。
• わざわざ関数を作るまでもねえだろ、暇人！と思うじゃん？
• 意外と奥が深い、というほど深くもないけど、目からウロコな感じはあるから、紹介するね。

べき乗計算の計算量(シンプル版)

• 深く考えず、本能の赴くままにコードを書くとこんな感じ

func pow(_ a:Int,_ n:Int)->Int {
    var ans = 1
    for i in 0..<n {
        ans *= a
    }
    return ans
}

print(pow(11,3)) // 1331
print(pow(3,33)) // 5559060566555523

• はい終了...んなわきゃない。
• まあ、間違ってはないけど、間違ってはないんだけど、これだと効率面で駄目なのね。
• 例えば、現実で使う場面があるかどうか分からないけど、nが$10^{10}$の場合は、計算できるだろうか？
• もちろん、数が大きくなりすぎて、Intでは桁が足りないという問題はあるから、mod998244353で計算する前提としても、計算量が競技プログラミングの標準的な目安である$10^8$を大きく超えてしまうため、計算が出来ないよね。

繰り返し二乗法

• 「繰り返し二乗法」とは、べき乗計算の計算量を減らす方法の名前です。
• 例えば、nが0〜255の範囲の数字の時、nは下記のように書ける。なお、i0～i7はそれぞれ0か1。
• $ n = 1×i0 + 2×i1 + 4×i2 + 8×i3 + 16×i4 + 32×i5 + 64×i6 + 128×i7 $
• 具体例を言えば、127 = 1+2+4+8+16+32+64 と書けるよね。
• pow(7,127)を解く場合、最初のアルゴリズムを使うと、計算量は127となるけど、127 = 1+2+4+8+16+32+64 となることを利用して、下記のように計算量を削減できる。
  • まず、分解します。
    • $7^{127} = 7^{1+2+4+8+16+32+64} = 7^1×7^2×7^4×7^8×7^{16}×7^{32}×7^{64}$
  • べき乗計算をそれぞれ行います。
    • $7^1 = 7$ -- ①
    • $7^2 = (7^1)^2$ -- ②
    • $7^4 = (7^2)^2$ -- ③
    • $7^8 = (7^4)^2$ -- ④
    • $7^{16} = (7^8)^2$ -- ⑤
    • $7^{32} = (7^{16})^2$ -- ⑥
    • $7^{64} = (7^{32})^2$ -- ⑦
  • 上記の①〜⑦を乗じます。
  • 上記の例だと、計算量は2×7 = 14 となり、当初アルゴリズムによる127から大幅に削減できたよね。このアルゴリズムを繰り返し二乗法と呼びます。
• 実際にコードを書く。もちろん、大きな数字に対応できるよう、mod998244353表示にするね。
• 比較用にシンプル版のmod998244353表示のコードを書くと

func pow(_ a:Int,_ n:Int)->Int {
    var ans = 1
    let mod = 998244353
    for i in 0..<n {
        ans *= a
        
        //mod998244353
        if ans > mod {ans = ans % mod}
    }
    return ans
}

print(pow(11,3)) // 1331
print(pow(3,33)) // 478528062
print(pow(7,127)) // 561762571

• 繰り返し二乗法のコードを書くと

func pow(_ a:Int,_ n:Int)->Int {
    var ans = 1
    var x = a
    var i = n
    let mod = 998244353
    while i > 0 {
        if i % 2 == 1 {ans *= x}
        x *= x
        i >>= 1
        
        //mod998244353
        if ans > mod {ans = ans % mod}
        if x > mod {x = x % mod}
    }
    return ans
}

print(pow(11,3)) // 1331
print(pow(3,33)) // 478528062
print(pow(7,127)) // 561762571

• うむ、大成功！
• ところで、「mod998244353って、なんじゃらほい？」と思った人がいたら、modの公式 を参考にしてほしい。

さいごに

• 計算量は最初のアルゴリズムでO(n)だったのに対し、繰り返し二乗法では、O(log n)となり、高速化が図れる。c++やpythonで実装されているpowでは繰り返し二乗法を取り入れているから、swiftでシンプルな累乗計算してしまうと、計算量で差を付けられてしまうので注意。