高速なべき乗の計算

『Essential Algorithms: A Practical Approach to Computer Algorithms』にべき乗の計算を高速にする方法について書かれていた。

ナイーブに計算すると、べき乗の計算は乗数が増えたときに遅くなる。次のべき乗の基本的な法則を活用して、これを解消できる。

• $A^{2 \times M} = (A^M)^2$
• $A^{(M + N)} = A^M \times A^N$

例として挙げられていたものは、$7^6$ の計算である。まずは、次のような計算をする。

• $7^1 = 7$
• $7^2 = (7^1)^2 = 49$
• $7^4 = (7^2)^2 = 49^2 = 2401$

ここで $7^6 = 7^4 \times 7^2$ だから、$49 \times 2401 = 117649$ が答えとなる。

素直に $7 \times 7 \times 7 \times 7 \times 7 \times 7$ とすると、7回の乗算が必要だけど、この方法だと乗算が3回しか発生しない。

この実装を Python で書いてみたけど、あまり速くはならなかった。うーん、なんでだろう。

#!/usr/bin/env python2

import collections


def my_pow(x, y):
    n_powered = collections.OrderedDict({})

    idx = 1
    mult = x
    while idx < y:
        n_powered[idx] = mult

        mult = mult * mult
        idx = idx * 2

    rev_keys = sorted(n_powered.keys(), reverse=True)

    result = 1
    for key in rev_keys:
        if key <= y:
            result *= n_powered[key]
            y -= key

    return  result


def naive_pow(x, y):
    result = 1
    for i in range(y):
        result *= x
    return result


print my_pow(7, 10000)
print naive_pow(7, 10000)