7

私は、C# コードを使用して Lucas-Lehmer 素数性テストを最適化する作業を行ってきました (はい、完全数を計算するためにメルセンヌ素数を使用しています。現在のコードでさらに速度を改善できるのではないかと考えていました。数値を保持するための System.Numerics.BigInteger クラス。おそらくこれは賢明ではありません。

このコードは、実際にはhttp://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_testにあるインテリジェンスに基づいています。

このページ (タイムスタンプ) セクションでは、分割を最適化するためのいくつかの証拠が示されています。

LucasTest のコードは次のとおりです。

public bool LucasLehmerTest(int num)
{
  if (num % 2 == 0)
     return num == 2;
  else
  {
     BigInteger ss = new BigInteger(4);
     for (int i = 3; i <= num; i++)
     {
        ss = KaratsubaSquare(ss) - 2;
        ss = LucasLehmerMod(ss, num);
     }
     return ss == BigInteger.Zero;
  }

}

編集:以下のMare Infinitus によって提案されているように、BigInteger クラスの ModPow を使用するよりも高速です。その実装は次のとおりです。

public bool LucasLehmerTest(int num)
{
  if (num % 2 == 0)
     return num == 2;
  else
  {
     BigInteger m = (BigInteger.One << num) - 1;
     BigInteger ss = new BigInteger(4);
     for (int i = 3; i <= num; i++)
       ss = (BigInteger.ModPow(ss, 2, m) - 2) % m;
     return ss == BigInteger.Zero;
  }

}

LucasLehmerMod メソッドは次のように実装されます。

public BigInteger LucasLehmerMod(BigInteger divident, int divisor)
{
   BigInteger mask = (BigInteger.One << divisor) - 1;  //Mask
   BigInteger remainder = BigInteger.Zero;
   BigInteger temporaryResult = divident;

   do
   {
      remainder = temporaryResult & mask;
      temporaryResult >>= divisor;
      temporaryResult += remainder;
   } while ( (temporaryResult >> divisor ) != 0 );

   return (temporaryResult == mask ? BigInteger.Zero : temporaryResult);
}

私が恐れているのは、.NET フレームワークから BigInteger クラスを使用すると、それらの計算に拘束されることです。それを改善するには、独自の BigInteger クラスを作成する必要があるということですか? または、このようにKaratsubaSquare (Karatsuba アルゴリズムから派生したもの) を使用して維持できますか?

public BigInteger KaratsubaSquare(BigInteger x)
{
   int n = BitLength(x);                                 

   if (n <= LOW_DIGITS) return BigInteger.Pow(x,2);        //Standard square

   BigInteger b = x >> n;                                  //Higher half
   BigInteger a = x - (b << n);                            //Lower half
   BigInteger ac = KaratsubaSquare(a);                     // lower half * lower half
   BigInteger bd = KaratsubaSquare(b);                     // higher half * higher half
   BigInteger c = Karatsuba(a, b);                         // lower half * higher half

   return ac + (c << (n + 1)) + (bd << (2 * n));          
}

基本的には、for ループを最適化することで、Lucas-Lehmer のテスト方法を改善できるかどうかを調べたいと思います。しかし、私はそこに少し立ち往生しています...それは可能ですか?

もちろん、どんな考えでも大歓迎です。

いくつかの追加事項：

複数のスレッドを使用して、完全数を見つける計算を高速化できます。ただし、適切なパーティショニングについては (まだ) 経験がありません。私は自分の考えを説明しようとします（コードはまだありません）：

最初に、エラトステネスの篩を使用してプライムテーブルを生成します。シングル スレッドで 2 ～ 100 万の範囲内の素数を見つけるには、約 25 ミリ秒かかります。

C# が提供するものは非常に驚くべきものです。Parallel.For メソッドで PLINQ を使用すると、いくつかの計算をほぼ同時に実行できましたが、primeTable 配列がチャンクされて、検索に反映されません。

このタスクには、スレッドの自動負荷分散では不十分であることはすでにわかっています。したがって、メルセンヌ数に応じて負荷バランスを分割し、完全数を計算するために使用する別のアプローチを試す必要があります。誰かこれを経験したことがありますか？このページは少し役立つようです: http://www.drdobbs.com/windows/custom-parallel-partitioning-with-net-4/224600406

さらに調べてみます。

今のところ、私の結果は次のとおりです。私の現在のアルゴリズム (C# の標準 BigInteger クラスを使用) は、ラップトップ (4 コアと 8GB の Intel I5) で最初の 17 個の完全数 ( http://en.wikipedia.org/wiki/List_of_perfect_numbersを参照) を 5 秒以内に見つけることができます。 RAMの）。ただし、その後スタックし、10 分以内に何も見つかりません。

これはまだ一致させることができないものです... 私の直感 (および常識) は、18 番目の完全数 (Mersenne Prime 3217 を使用) を計算する for ループが 3214 回実行されるため、LucasLehmer テストを調べる必要があることを教えてくれます。改善の余地はあると思います...

Dinony が以下に投稿したのは、C で完全に書き直すという提案です。パフォーマンスが向上することに同意しますが、C# を選択して、その制限と利点を見つけました。広く使用されており、アプリケーションを迅速に開発できるため、試してみる価値があるように思えました。

安全でないコードはここでも利点を提供できますか?

4

3 に答える 3

1

コードを C に適合させるのはどうですか? アルゴリズムについてはわかりませんが、それほど多くのコードではありません..したがって、ランタイムの最大の改善はCに適応することです.

于 2013-05-10T15:42:21.977 に答える