バイナリ法

バイナリ法（英語には同等の用語は無いらしい）は、べき乗を高速に求める方法です。実際には乗算以外にも色々使えるので、必ず覚えておきましょう。
例えば、3の8乗を求めるとき、

6561 = 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3

とすると7回の乗算が必要ですが、

9 = 3 × 3
81 = 9 × 9
6561 = 81 × 81

とすれば3回の乗算で済みます。
これは指数が2のべき乗のときですが、一般の場合は次のようにします。例えば、a¹¹を計算するとき、まず11を2進で表して、

1011

これに対応して、1が立っているところを計算して、掛け合わせます。

a⁸ a² a¹

計算の手順としては、

y = 1
z = a
y = y * z
z = z * z   # a²
y = y * z   # a³
z = z * z   # a⁴
z = z * z   # a⁸
y = y * z   # a¹¹

で、実質5回の乗算で11乗が計算できます。

def pow(x, n):

    y = 1

    z = x

    while n:

        if n & 1:

            y *= z

        z *= z

        n >>= 1

    return y
print pow(3, 11)

これは再帰で書くとよりきれいに書けます。

def pow(x, n):

    if n == 0:

        return 1

    

    y = pow(x, n / 2)

    z = y * y

    if n & 1:

        z *= x

    return z
print pow(3, 11)

再帰で書くのは、特にC++などのtemplate機能を使うときに威力を発揮します。

#include 
using namespace std;
template

int pow(int x) {

    if(N == 0)

        return 1;

    

    int y = pow(x);

    int z = y * y;

    if(N & 1)

        z *= x;

    return z;

}
int main() {

    cout << pow<11>(3) << endl;

}

あらかじめ指数を指定しておくと、分岐の必要がなくなり高速化が期待できます。

より高速な方法

バイナリ法は、乗算の回数の最適化という意味では必ずしも最も速い方法ではありません。例えば、15乗を計算するとき、バイナリ法では、

y = 1
z = a
y = y * z
z = z * z # a²
y = y * z # a³
z = z * z # a⁴
y = y * z # a⁷
z = z * z # a⁸
y = y * z # a¹⁵

と、実質6回の乗算が必要ですが、

y = 1
z = a
y = y * z
z = z * z # a²
z = y * z # a³
u = z * z # a⁶
u = u * u # a¹²
y = z * u # a¹⁵

と、5回の乗算で計算できます。