私は、C# で最大の主要なプログラミング プラクティスの問題を解決しようとしています。問題は単純で、数値を印刷するかファイルに書き込んでください: 2 57,885,161 − 1 (17,425,170 桁)
Emil Stevanof .Netラッパーを介して、驚くべきGNU Multiple Precision Arithmetic Libraryを使用して解決することができました
var num = BigInt.Power(2, 57885161) - 1;
File.WriteAllText("biggestPrime.txt", num.ToString());
現在投稿されているすべてのソリューションがこのライブラリを使用していても、私には不正行為のように感じます. マネージド コードでこれを解決する方法はありますか? アイデア？提案？
PS: 既に .Net 4.0 BigIntegerを使用してみましたが、計算が終了することはありません(5 分待ちましたが、50 秒の GMP ソリューションと比較すると、既に多くの時間を費やしています)。
これも解決策というよりはチートですが、IntX ライブラリを使用してこれを解決しました
IntX.Pow(2, 57885161, MultiplyMode.AutoFht) - 1;
約6分間走りました。それでも、これは本当の答えではありません。「本物」を見るのは面白いでしょう。
編集: C# ストップウォッチを使用すると、計算に 5 秒しかかからないことがわかりました。非常に時間がかかるのは ToString のプロセスです。
乗算 (および適切な大きな整数ライブラリ) だけを使用してこの数を計算する場合は、計算の回数を減らすことを検討できます。単純なケースでは、1 を推測する前に 2 を繰り返し (57885161 回) 掛けることができますが、はるかに少ない掛け算でそれを行うことができます。
二乗の繰り返しを考えてみましょう。これにより、 2, 2 2 , (2 2 ) 2 = 2 4 , (2 4 ) 2 = 2 8などが得られます.25回二乗すると、 2 (2 25 ) = 2 33554432と計算されます.
57885161 の 2 進数表現を見ると、11011100110100000111101001 が得られます。つまり、(2 57885161の場合) 2 (2 25 ) * 2 (2 24 ) * 2 (2 22 )などが必要であることがわかります。必要な最高のものを計算する途中で 2 の累乗を計算し、最終的な乗算を行います。つまり、25 + 13 の大きな整数の乗算です。次に、必要な値を 1 差し引く必要があります。
何を達成するかは、計算集約的です。Visual C# と Visual Basic (および一般的なインタープリター言語) は、そのような目的のために設計されていません。GMP は純粋な C で実装され、実行速度が高度に最適化されているため、GMP を使用するのが適切です。
マネージド コードのみを使用する場合は、しばらくお待ちください。.Net 4.0 BigInteger を使用すると、GMP を使用する場合よりも最大100 倍の時間がかかる場合があります。これをテストするには、.Net 4.0 フレームワークを使用して 2 1,000、2 10,000、2 100,000、2 1,000,000、および 2 10,000,000を計算し、これらの各式の計算にかかる時間を確認する必要があります。
必要な時間が長すぎることが判明した場合は、自分で計算を試みることができます。このアルゴリズムを使用して累乗を実行してから、C++ から C# に移植する必要があります。私自身の大きな整数乗算の実装または他のものを見つけることができます。ただし、依然としてマネージ コードを使用しているため、パフォーマンスが大幅に向上するという保証はありません。