求幂的分治法？
作为家庭作业，我应该实施一种分而治之的方法来计算大整数的幂。我知道 Karatsuba 的乘法算法，我可以应用什么分而治之算法来获得 x^y 的结果，两者都是大整数？
As homework, I should implement a divide and conquer approach for exponentiation of big integers. I know Karatsuba's algorithm for multiplication, what divide and conquer algorithm could I apply to get the result of x^y, both being large integers?.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
有几种算法以平方和乘法的名称组合在一起。你可以从他们身上得到一些灵感。
There are a couple of algorithms grouped together under the name square and multiply. You could get some inspiration from them.
考虑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^2)^2)^2...)^2 仅仅 8次（256 的 log2）。一般来说，将指数写成二进制并应用指数求和规则，然后在计算 x 的连续幂时，如果它们出现在指数中，则将它们相乘到累加器中。如果指数中的该数字中有“1”，则出现）
请参阅 http://en.wikipedia .org/wiki/Exponentiation_by_squaring
Consider x^256. Rather than doing
x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x, one could do (...(((x^2)^2)^2...)^2 a mere 8 times (log2 of 256).In general, write out your exponent as binary and apply the exponent-of-sum rule. Then as you calculate successive powers of x, multiply them in to an accumulator if they appear in the exponent (they will appear if there is a "1" in that digit in the exponent).
See http://en.wikipedia.org/wiki/Exponentiation_by_squaring
这是一个很好的递归算法。
Here's a nice recursive algorithm.