快速求幂实现
有人可以指出一个网站，我可以在其中找到一种使用 C# 有效计算大幂整数幂的算法吗？
例如。我想计算 2^60000 或 3^12345
Could someone please point out a site where I can find an algorithm to efficiently calculate integer exponentiation to large powers using C#?
eg. I want to calculate 2^60000 or 3^12345
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
除非这是家庭作业，否则您可能不想自己实现任意精度求幂。计算您所描述的类型的大指数很复杂 - 撇开性能不谈。
我建议使用现有的任意精度算术库之一，例如 GMP - 其中大部分有库可以从 C# 访问它们。
F# 支持使用 BigInt 类进行任意精度算术（如果导入它所在的程序集，也可以从 C# 访问该类）。但是，我不知道 BigInt 求幂的优化程度如何。
如果您只是想了解有效的求幂算法，您可能需要研究Square-And-用于求幂的乘法算法。
Unless this is homework, you probably don't want to roll your own implementation of arbitrary precision exponentiation. Calculating large exponents of the type you describe is complicated - performance aside.
I would recommend using one of the existing arbitrary precision arithmetic libraries, like GMP - most of which have libraries to access them from C#.
F# has support for arbitrary precision arithmetic using the BigInt class (which you can also access from C# if you import the assembly it's in). However, I don't know how optimized BigInt exponentiation is.
If you're simply trying to learn about efficient algorithms for exponentiation, you may want to look into the Square-And-Multiply algorithm for exponentiation.
可以使用称为“平方求幂”链接的方法有效地计算整数幂。
该方法还可以用于计算模幂链接，用于一些非对称加密中类似 RSA 的方法。
Integer exponentiation can effectively be calculated using a method known as "Exponentiation by squaring" link.
This method can also be used to calculate the modular exponentiation link, which is used in some asymmetric encryption methods like RSA.
看看这个：IntX 用于处理大整数。您可能必须编写自己的 power 实现，但由于支持乘法，因此这应该不那么难。
280Z28 编辑：另一个包含快速 Pow、ModPow 和素性测试的实现是 BigInteger< /a> 实现（代码项目），我过去曾在 Project Euler 问题上使用过它 - 尽管我现在使用 .NET 4.0 并使用它的 System.Numerics.BigInteger 实现。
Check this out: IntX for working with LARGE integers. You might have to write your own implementation of power, but since multiplication is supported, this should not be so hard.
Edit by 280Z28: Another implementation which includes fast Pow, ModPow, and primality testing is this BigInteger implementation (Code Project), which I've used on Project Euler problems in the past - though I now work with .NET 4.0 and use its System.Numerics.BigInteger implementation.