累乗高速計算

累乗を計算することがあって、まじめにn回掛け算をしていた。
どうやら素早く計算するアルゴリズムがあるようなのでそれを実装した。

たとえば2^11を計算するときは
2^11 = 2^0 * 2^1 * 2^2 * 2^8
　　　= 1 * 2 * 4 * 256
と計算すれば4回の掛け算で表すことができる。

def power(b, n):
    if n == 0:
        return 1
    elif n%2:
        return b*power(b, n-1)
    else:
        return power(b*b, n/2)

def ntimes(b,n):
    ret = 1
    for i in xrange(n):
        ret *= b
    return ret

if __name__ == "__main__":
    b = 2    
    n = 50    
    rep = 100000
    #print ntimes(b,n), power(b,n)
    
    from timeit import Timer
    t = Timer("ntimes(%d,%d)" % (b, n), "from __main__ import ntimes") 
    print t.timeit(rep)
    
    t = Timer("power(%d,%d)" % (b, n), "from __main__ import power") 
    print t.timeit(rep)