c# - 快速求幂实现

Question

有人可以指出一个网站，我可以在其中找到一种算法来使用 C# 有效地计算整数幂幂吗？

例如。我想计算 2^60000 或 3^12345

Answer 1

除非这是家庭作业，否则您可能不想滚动自己的任意精度求幂实现。计算您描述的类型的大指数很复杂 - 除了性能。

我建议使用现有的任意精度算术库之一，如 GMP - 其中大多数都有库可以从 C# 访问它们。

F# 支持使用 BigInt 类的任意精度算术（如果导入它所在的程序集，也可以从 C# 访问该类）。但是，我不知道 BigInt 求幂的优化程度如何。

如果您只是想了解有效的求幂算法，您可能需要研究求幂的Square-And-Multiply算法。

Answer 2

整数取幂可以使用称为“平方取幂”链接的方法有效地计算。

这种方法也可以用来计算模幂链接，在一些非对称加密方法如RSA中使用。

Answer 3

看看这个：IntX用于处理 LARGE 整数。您可能必须编写自己的幂实现，但由于支持乘法，所以这不应该那么难。

由 280Z28 编辑：另一个包含快速 Pow、ModPow 和素数测试的实现是这个BigInteger实现（代码项目），我过去曾在 Project Euler 问题上使用过它——尽管我现在使用 .NET 4.0 并使用它的系统.Numerics.BigInteger实现。