快速求幂的实现

Question

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

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

Answer 1

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

我会推荐使用existing arbitrary precision arithmetic libraries, like GMP之一 - 其中大部分都有库从C＃访问它们。

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

如果您只是想了解指数运算的高效算法，您可能需要查看指数运算的Square-And-Multiply算法。

Answer 2

查看结果：IntX适用于LARGE整数。你可能必须编写自己的权力实现，但由于支持乘法，所以这不应该太难。

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

Answer 3

整数求幂可以有效地使用称为“平方的求幂运算”的方法来计算link。

此方法也可用于计算模幂运算link，它用于某些非对称加密方法（如RSA）。