べき乗

昨日のコードでべき乗の計算を、10をn回掛けて行っていたが、Pythonはこれでよかったんだった。

a = 10**n

これだけでは面白くないので、再帰のコードを考えてみた。

def pow(a, n):

    if n > 1:

        half = n >> 1

        return pow(a, half) * pow(a, n - half)

    elif n == 1:

        return a

    elif n == 0:

        return 1

    else:

        return 0
print pow(10, 100)

例えば、2⁹を計算するときに、半分にわけて考える。

2⁹ = 2⁴ * 2⁵

こうやって分けていくと、いつか1乗になる。
ベンチマークしてみると、

import time
def pow(a, n):

    if n > 1:

        half = n >> 1

        return pow(a, half) * pow(a, n - half)

    elif n == 1:

        return a

    elif n == 0:

        return 1

    else:

        return 0
n = 100000

t1 = time.clock()

a = 10**n

t2 = time.clock()

b = pow(10, n)

t3 = time.clock()

c = 1

for i in range(n):

    c *= 10

t4 = time.clock()
print "%.4fs %.4fs %.4fs" % (t2 - t1, t3 - t2, t4 - t3)

0.0973s 0.4354s 4.8172s

再帰を使うと、単純に掛けていくだけよりは圧倒的に速いが、**より圧倒的に遅い。
**はバイナリ法を使っているのだろうか。