c# - 高速累乗の実装

Question

C# を使用して整数の冪乗を効率的に計算するアルゴリズムを見つけることができるサイトを教えてください。

例えば。2^60000 または 3^12345 を計算したい

Answer 1

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

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

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

べき乗の効率的なアルゴリズムについて単に学習しようとしている場合は、べき乗のSquare-And-Multiplyアルゴリズムを調べることをお勧めします。

Answer 2

これをチェックしてください：LARGE整数を操作するためのIntX 。独自のpowerの実装を作成する必要があるかもしれませんが、乗算がサポートされているため、これはそれほど難しいことではありません。

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