-
06-07-2019 - |
質問
誰かがC#を使用して整数のべき乗を効率的に計算するためのアルゴリズムを見つけることができるサイトを指摘してもらえますか?
eg。 2 ^ 60000または3 ^ 12345を計算したい
解決
これが宿題でない限り、任意精度の累乗の独自の実装をロールバックしたくないでしょう。記述したタイプの大きな指数の計算は複雑です-パフォーマンスは別です。
GMPなどの既存の任意精度の算術ライブラリーのいずれかを使用することをお勧めします-ほとんどにはC#からアクセスするライブラリがあります。
F#は、BigIntクラスを使用して任意精度の計算をサポートしています(アセンブリをインポートすると、C#からもアクセスできます)。ただし、BigIntのべき乗が最適化されているかどうかはわかりません。
べき乗の効率的なアルゴリズムについて単に学習しようとしている場合は、 Squareをご覧ください。 -べき乗のアルゴリズム。
他のヒント
これをチェックアウトします。 IntX を使用して大きな整数を処理します。独自のパワー実装を作成する必要があるかもしれませんが、乗算がサポートされているため、これはそれほど難しくないはずです。
280Z28による編集:高速パウ、ModPow、および素数テストを含む別の実装は、これです BigInteger 実装(コードプロジェクト)。これは、過去にProject Eulerの問題で使用したものですが、現在は.NET 4.0で作業し、その System.Numerics.BigInteger の実装。
所属していません StackOverflow