C＃で素数を計算する最速の方法は？

Question

私は実際に私の質問に答えているが、並列化されていないので、アルゴリズムを改善する方法に興味がある。とにかく、それはある人にとっては現状のままで役に立つかもしれません。

int Until = 20000000; 
BitArray PrimeBits = new BitArray(Until, true); 

/* 
* Sieve of Eratosthenes 
* PrimeBits is a simple BitArray where all bit is an integer 
* and we mark composite numbers as false 
*/ 

PrimeBits.Set(0, false); // You don't actually need this, just 
PrimeBits.Set(1, false); // remindig you that 2 is the smallest prime 

for (int P = 2; P < (int)Math.Sqrt(Until) + 1; P++) 
    if (PrimeBits.Get(P)) 
     // These are going to be the multiples of P if it is a prime 
     for (int PMultiply = P * 2; PMultiply < Until; PMultiply += P) 
      PrimeBits.Set(PMultiply, false); 

// We use this to store the actual prime numbers 
List<int> Primes = new List<int>(); 

for (int i = 2; i < Until; i++) 
    if (PrimeBits.Get(i)) 
     Primes.Add(i); 

たぶん私はそれらを一緒に複数のBitArray Sを使用してBitArray.And()だろうか？

Answer 1

ビット配列を二重リンクリストで相互参照することで時間を節約できるため、素早く次のプライムに進むことができます。

また、最初に新しい素数pをヒットした後の合成を削除する際には、残りのpの最初の合成倍数はp * pになります。実際には、リストの後に残っている残りのすべての素数でpを乗算するだけで、製品が範囲外（Untilより大きい）になるとすぐに停止する必要があります。

Miller-Rabinテストなど、いくつかの優れた確率論的アルゴリズムもあります。 The wikipedia pageは良い紹介です。

Answer 2

パラレル化とは別に、すべての反復でsqrt（Until）を計算したくありません。 2,3、および5の倍数を仮定することができ、{1,7,11,13,17,19,23,29}の{1,5}またはN％30でN％6のみを計算することもできます。

N番目のステージはsqrt（n）番目の結果にのみ依存するため、因数分解アルゴリズムを非常に簡単に並列化できるはずです。しばらくすると、競合は発生しません。しかし、それは多くの分割を必要とするので、良いアルゴリズムではありません。

読み取り前に完了することが保証されているライター作業パケットがある場合は、ふるいアルゴリズムを並列化することもできます。ほとんどの場合、ライターは読者と競合すべきではありません。少なくとも少数のエントリーを済ませたら、読者の少なくともN人で作業する必要があります。したがって、時折同期読み取りが必要になります（Nが最後に同期読み取り値）。書き込み競合が発生しないため、bool配列を任意の数のライタースレッド間で同期させる必要はありません（最悪の場合、複数のスレッドが同じ場所に真を書き込む）。

主な問題は、書き込み待ちのワーカーが確実に完了することです。 C++では、比較と設定を使用して、いつでも待っているワーカーに切り替えることができます。私はC＃wonkではないので、その言語を行う方法はわかりませんが、Win32のInterlockedCompareExchange関数が利用できるはずです。

アクターベースのアプローチを試してみてください。最低値で作業するアクターをスケジュールすることができます。これにより、バスをロックすることなくふるいの有効な部分を読み取ることがより簡単になる場合があります

いずれにしても、読者はすべての従業員がNを超えていることを確認しなければなりません。そのコストは、並列とシリアルのトレードオフが行われる場所です。

Answer 3

@DrPizzaプロファイリングは、実装の改善に役立ちますが、並列実行の機会を明らかにしたり、より良いアルゴリズムを提案したりしません（そうしないと経験がない限り、プロファイラを見たい）。

私は家庭ではシングルコアマシンしか持っていませんでしたが、BitArrayシーブのJava対応版と、篩の反転のシングルスレッド版 - マーキング素数を配列に保持し、wheelを使用してサーチスペースを5分の1に減少させ、各マーキングプライムを使用してホイールのインクリメントでビットアレイをマーキングする。 O（N）の代わりにストレージをO（sqrt（N））に減らすことで、最大のN、ページング、および帯域幅の両方に役立ちます。

N（1e8〜1e12）の中程度の値の場合、非常に素早くsqrt（N）までの素数を見つけることができます。その後、CPUでの後続の検索を非常に簡単に並列化できるはずです。私のシングルコアマシンでは、ホイールアプローチは28秒で1e9までの素数を見つけますが、あなたのふるい（ループからsqrtを移動した後）は86秒かかるのですが、改善はホイールによるものです。反転は、2^32より大きいNを扱うことができますが、それをより遅くすることを意味します。コードはhereです。ビット配列がその点の後に変更されないので、あなたはsqrt（N）を過ぎた後に素朴なふるいからの結果の出力を並列化することができます。しかし、一度Nの大きさを十分に扱っていれば、配列のサイズはintには大きすぎます。

Answer 4

プロファイリングなしでは、最適化が必要なプログラムのビットを特定できません。

大規模なシステムでは、プロファイラを使用して素数生成プログラムが最適化が必要な部分であることがわかります。

ダースンなどの命令でループをプロファイリングするのは、通常は価値がありません。プロファイラーのオーバーヘッドはループ本体と比較して重要であり、ループを改善する唯一の方法はアルゴリズムを変更することです反復回数を少なくする。したがって、IMEでは、高価な機能を排除し、数行の簡単なコードをターゲットにしていれば、命令レベルでコードを改善しようとするよりも、アルゴリズムを変更してエンドツーエンドのタイミングを調整する方がよいプロファイリング

Answer 5

また、algorithmsの変更を考慮する必要があります。

リストに要素を追加するだけで簡単に要素を追加する方が安価かもしれないと考えてください。

リストのスペースをあらかじめ割り当てておくと、ビルド/ポピュレートが安くなるでしょう。

Answer 6

新しい素数を見つけようとしていますか？これは愚かに聞こえるかもしれませんが、あなたは既知の素数で何らかの種類のデータ構造をロードすることができます。私はそこに誰かがリストを持っていると確信しています。新しい数値を計算する既存の数値を見つける方がはるかに簡単な問題かもしれません。

また、MicrosoftのParallel FX Libraryを参照すると、既存のコードをマルチスレッドシステムでマルチコアシステムを利用できるようにすることができます。コードの変更を最小限に抑えて、マルチスレッドのループを作成することができます。

Answer 7

エラトステネスのふるいについては非常に良い記事があります：The Genuine Sieve of Eratosthenes

は、機能設定でだが、opimizationのほとんどはまた、C＃での手続きの実装に適用されます。

2つの最も重要な最適化は、2 * Pの代わりにP^2で交差を開始し、次の素数にホイールを使用することです。

並行処理のために、P^2までのすべての数値をPと並行して処理することができます。

Answer 8

void PrimeNumber(long number) 
    { 
     bool IsprimeNumber = true; 
     long value = Convert.ToInt32(Math.Sqrt(number)); 
     if (number % 2 == 0) 
     { 
      IsprimeNumber = false; 
      MessageBox.Show("No It is not a Prime NUmber"); 
      return; 
     } 
     for (long i = 3; i <= value; i=i+2) 
     {    
      if (number % i == 0) 
      { 

       MessageBox.Show("It is divisible by" + i); 
       IsprimeNumber = false; 
       break; 
      } 

     } 
     if (IsprimeNumber) 
     { 
      MessageBox.Show("Yes Prime NUmber"); 
     } 
     else 
     { 
      MessageBox.Show("No It is not a Prime NUmber"); 
     } 
    }