快速取幂实现

Question

有人可以指出一个网站，我可以找到一个算法，使用C＃有效地计算整数取幂到大功率？

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

Answer 1

除非这是作业，否则你可能不希望自己实现任意精度取幂。计算你描述的类型的大指数是复杂的 - 除了性能。

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

F＃支持使用BigInt类进行任意精度算术运算（如果导入其中的程序集，也可以从C＃访问）。但是，我不知道BigInt取幂的优化程度如何。

如果您只是想了解有效的取幂算法，您可能需要查看 Square求和的求和算法。

Answer 2

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

此方法也可用于计算模幂运算链接，用于一些非对称加密方法，如RSA。

Answer 3

检查一下： IntX ，用于处理LARGE整数。你可能必须编写自己的权力实现，但由于支持乘法，这应该不会那么难。

编辑280Z28：另一个包含快速Pow，ModPow和素性测试的实现是 BigInteger 实现（Code Project），我过去曾用过Project Euler问题 - 虽然我现在使用.NET 4.0并使用它的 System.Numerics.BigInteger 实施。