指数运算的分治法？

Question

作为作业，我应该实现一个大整数指数幂的分治算法。我知道卡拉图巴乘法算法，那么我可以应用什么分治算法来得到x^y的结果？

- andandandand

Answer 1

有几个算法被归为平方乘算法。你可以从中获得一些灵感。

- Femaref

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，可以进行 8 次幂运算 (256 的 log2)。

一般来说，将指数转换为二进制并应用幂的加法规则。然后，当计算x的连续幂时，如果它们出现在指数中（如果该数字在指数中为“1”），则将它们乘入累加器中。请参见http://en.wikipedia.org/wiki/Exponentiation_by_squaring。

- ninjagecko

---

指数和规则是什么？ - andandandand

你是在问维基百科链接中的2^k-ary方法，对吗？ - andandandand

表达式 (((x^2)^2)^2) 等于 x^8 而不是 x^256。 - Javier Ruiz

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);
}

- Rezo Megrelidze