快速求冪的實現

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）。