高速べき乗の実装

Question

誰かがC＃を使用して整数のべき乗を効率的に計算するためのアルゴリズムを見つけることができるサイトを指摘してもらえますか？

eg。 2 ^ 60000または3 ^ 12345を計算したい

Answer 1

これが宿題でない限り、任意精度の累乗の独自の実装をロールバックしたくないでしょう。記述したタイプの大きな指数の計算は複雑です-パフォーマンスは別です。

GMPなどの既存の任意精度の算術ライブラリーのいずれかを使用することをお勧めします-ほとんどにはC＃からアクセスするライブラリがあります。

F＃は、BigIntクラスを使用して任意精度の計算をサポートしています（アセンブリをインポートすると、C＃からもアクセスできます）。ただし、BigIntのべき乗が最適化されているかどうかはわかりません。

べき乗の効率的なアルゴリズムについて単に学習しようとしている場合は、 Squareをご覧ください。 -べき乗のアルゴリズム。

Answer 2

整数のべき乗は、「二乗による指数」として知られる方法を使用して効果的に計算できます。 リンク。

この方法は、モジュラーべき乗の計算にも使用できますリンク RSAなどの非対称暗号化方式。

Answer 3

これをチェックアウトします。 IntX を使用して大きな整数を処理します。独自のパワー実装を作成する必要があるかもしれませんが、乗算がサポートされているため、これはそれほど難しくないはずです。

280Z28による編集：高速パウ、ModPow、および素数テストを含む別の実装は、これです BigInteger 実装（コードプロジェクト）。これは、過去にProject Eulerの問題で使用したものですが、現在は.NET 4.0で作業し、その System.Numerics.BigInteger の実装。