algorithm - 求幂的分治法？

Question

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

Answer 1

有几个算法以square 和 multiply的名称组合在一起。你可以从他们那里得到一些启发。

Answer 2

考虑 x^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^2)^2)^2...)^2 8 次（log2 of 256）。

通常，将您的指数写为二进制并应用指数和规则。然后，当您计算 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);
}