高速指数計算(べき乗)アルゴリズム

ある数の大きなべき数を計算を行う際にできるだけ少ない計算量で行うための方法として、高速指数計算法というものがある。

例えば、
$7 ^ {1281}$
を計算したいとする。ここで
$1281 = 1 + 256 + 1024 = 2 ^ {0} + 2 ^ {8} + 2 ^ {10} = 2 ^ {0} \times 1 + 2 ^ {1} \times 0 + 2 ^ {2} \times 0 + \ldots + 2 ^ {10} \times 1$
のように2の累乗の足し算に分解する。
そして、 $7 ^ {1281} = 7 ^ {1} \times 7 ^ {256} \times 7 ^ {1024}$ を計算する。
この分解をプログラムで行う場合には、順番に値を2で割り算し、その値が奇数であるかどうか判定し、値が0になるまで繰り返せばよい。やってみよう。

0: 1281 -> odd $7 ^ {1}$
1: 640 -> even $7 ^ {2}$
2: 320 -> even $7 ^ {4}$
3: 160 -> even $7 ^ {8}$
4: 80 -> even $7 ^ {16}$
5: 40 -> even $7 ^ {32}$
6: 20 -> even $7 ^ {64}$
7: 10 -> even $7 ^ {128}$
8: 5 -> odd $7 ^ {256}$
9: 2 -> even $7 ^ {512}$
10: 1 -> odd $7 ^ {1024}$
11: 0 -> 終わり

oddの部分の7の冪乗部分の3つを掛け算すれば答えが得られるが、この繰り返し処理の中で、
7の冪乗の値は一つ前で計算した値の２乗になっているので、計算量が最小限に抑えられるのである。

再帰を使わずにswiftで書くとこんな感じになる。

func pow(e:Int) -> Int {
    var b:Int = 7
    var r:Int = 1
    while e > 1 {
        if isOdd(e) { r *= b }
        // 2乗する
        b = b * b
        // 2で割る
        e /= 2
    }
    return r * b
}

再帰を使った場合はこんな感じになる。

func pow(e:Int) -> Int {
    if e == 0 { return 1 }
    let s = pow(e/2)
    // 2乗する
    let r = s * s
    if isOdd(e) {
        return r * 7
    } else {
        return r
    }
}

$pow(1281) = pow(640) ^ {2} \times 7$
$pow(640) = pow(320) ^ {2}$
$pow(320) = pow(160) ^ {2}$
$pow(160) = pow(80) ^ {2}$
$pow(80) = pow(40) ^ {2}$
$pow(40) = pow(20) ^ {2}$
$pow(20) = pow(10) ^ {2}$
$pow(10) = pow(5) ^ {2}$
$pow(5) = pow(2) ^ {2} \times 7$
$pow(2) = pow(1) ^ {2}$
$pow(1) = 7$