1.简单递归

最简单的求幂算法是根据xⁿ=x*x^n-1，使用递归：

def foo(x,n):    if n==0:        return 1    else:        return x*foo(x,n-1)

这样求x的n次方，会进行n-1次乘法运算，n较大时效率很低。

2.高效递归

一种更高效的算法，可以将运算次数降到LogN的级别，由于：

xⁿ=x^n/2*x^n/2 ， n为偶数时

xⁿ=x^(n-1)/2*x^(n-1)/2*x ， n为奇数时

def foo(x,n):    if n==0:        return 1    else:        if n%2==0:            return foo(x,n/2)*foo(x,n/2)        else:            return foo(x,n/2)*foo(x,n/2)*x

可以将运算次数降到LogN的级别。

3.快速求幂

还有一种快速求幂算法，称为二进制法：

比如求x的21次方，21的二进制为10101,由于x²¹=x¹⁶*x⁴*x^1，可以看出根据二进制表示(10101)，每当遇到1时，则乘以x，从右向左前进一位则将x自乘。

def foo(x,n):    result=1    while n:        if (n&1):            result*=x        x*=x        n>>=1    return result

这个算法用来计算非常的大的数时是十分高效的。例如有很多的素数测试算法都是依赖这个算法的不同变式。

4.抽象化

然后在某个地方我看到一个很有意思的想法，就是把上面的算法中的自乘函数化：

def foo(x,n,i,func):    result=i    while n:        if (n&1):            result=func(result,x)        x=func(x,x)        n>>=1    return resultif __name__=='__main__':    print foo(2,16,1,lambda x,y:x*y)

这样求x的n次方就能用foo(x,n,1,lambda x,y:x*y)来运算了。

如果求x*n，相当于将x自加n次，可以用foo(x,n,0,lambda x,y:x+y)来运算：

def foo(x,n,i,func):    result=i    while n:        if (n&1):            result=func(result,x)        x=func(x,x)        n>>=1    return resultif __name__=='__main__':    print foo(2,16,0,lambda x,y:x+y)

如果要把某个字符x重复n次，可以用：

def repeat(x,n,i,func):    result=i    while n:        if (n&1):            result=func(result,x)        x=func(x,x)        n>>=1    return resultif __name__=='__main__':    print repeat('a',16,'',lambda x,y:x+y)

把一个列表复制n次：

def repeat(x,n,i,func):    result=i    while n:        if (n&1):            result=func(result,x)        x=func(x,x)        n>>=1    return resultif __name__=='__main__':    print repeat([1,2],16,[],lambda x,y:x+y)

参考自：