分而治之的求幂方法？

Question

作为家庭作业，我应该实现一种大整数求幂的分而治之的方法。我知道Karatsuba的乘法算法，我可以应用什么分治算法来得到x^y的结果，两者都是大整数？

Answer 1

有几种算法被组合在一起，命名为square and multiply。你可以从他们那里得到一些灵感。

Answer 2

考虑x^256。人们可以只做8次(x^2)^2)^2 (log2为256)，而不是做x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x。

通常，将指数写出为二进制，并应用求和指数规则。然后，当您计算x的连续幂时，如果它们出现在指数中，则将它们相乘到累加器中(如果指数中的该数字中有"1“，则会出现)。

请参阅http://en.wikipedia.org/wiki/Exponentiation_by_squaring

Answer 3

这里有一个很好的递归算法。

int pow(int a,int b)
{
    if(b == 0) return 1;
    else if(b % 2 == 0) return pow(a,b/2) * pow(a,b/2);
    else return a * pow(a,b-1);
}