べき乗（2）

バイナリ法ってなんとなく美しくなくて嫌いなのだが、ジョギングしながらぼんやり考えていたら、再帰なら割ときれいにかけることに気がついた。

import time
def pow(a, n):

    if n > 1:

        b = pow(a, n >> 1)

        if n & 1:   # odd

            return a * b * b

        else:

            return b * b

    else:

        return a
n = 100000

t1 = time.clock()

a = 10**n

t2 = time.clock()

b = pow(10, n)

t3 = time.clock()

微妙に**を使うより速い。

ところで、掛け算は同じ数字同士でするとそうでない場合に比べて速いはずである。

(ax + b) * (cx + d) = acx2 + (ad + bc)x + bd

(ax + b) * (ax + b) = a2x2 + (ab + ab)x + b2

上で掛け算が一つ減っている。

import time
n = 100000
a = 10 ** n

b = a - 1
t1 = time.clock()

c = a * a

t2 = time.clock()

d = a * b

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

0.1980s 0.3219s

確かに速くなる。しかし、

import time
n = 100000
a = 10 ** n

b = a - 1

e = b + 1
t1 = time.clock()

c = a * e

t2 = time.clock()

d = a * b

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

0.3216s 0.3249s

同じ変数でないと速くならないらしい。正確には、変数は違ってもいいが、アドレスは同じでなければならないらしい。