c# - Lucas Lehmer 优化

Question

我一直在努力使用 C# 代码优化 Lucas-Lehmer 素数测试(是的，我正在用 Mersenne 素数做一些事情来计算完美数。我想知道当前代码是否有可能进一步提高速度.我用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 算法)来维持，我在 Optimizing Karatsuba Implementation 上找到的:

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 测试方法。但是，我有点卡在那里……这有可能吗？

当然欢迎任何想法。

一些额外的想法:

我可以使用多个线程来加快计算完美数的速度。但是，我(还)没有良好分区的经验。我将尝试解释我的想法(还没有代码):

首先，我将使用 Erathostenes 筛法生成素数表。在 2 - 100 万个单线程范围内查找素数大约需要 25 毫秒。

C# 提供的功能非常惊人。将 PLINQ 与 Parallel.For 方法结合使用，我几乎可以同时运行多个计算，但是，它将 primeTable 数组分块为不符合搜索要求的部分。

我已经发现线程的自动负载平衡不足以完成这项任务。因此，我需要尝试一种不同的方法，根据梅森数来划分负载平衡，以找到并用于计算完美数。有没有人有这方面的经验？此页面似乎有点帮助:http://www.drdobbs.com/windows/custom-parallel-partitioning-with-net-4/224600406

我会进一步调查。

至于现在，我的结果如下。我当前的算法(使用 C# 中的标准 BigInteger 类)可以在我的笔记本电脑(具有 4 个内核和 8GB RAM 的 Intel I5)上的 5 秒内找到前 17 个完美数字(参见 http://en.wikipedia.org/wiki/List_of_perfect_numbers)。然而，然后它卡住了，在 10 分钟内什么也找不到。

这是我还无法匹配的东西...我的直觉(和常识)告诉我我应该研究 LucasLehmer 测试，因为计算第 18 个完美数(使用 Mersenne Prime 3217)的 for 循环会运行3214次。我想还有改进的余地...

Dinony 在下面发布的建议是用 C 完全重写它。我同意这会提高我的性能，但是我选择 C# 是为了了解它的局限性和优势。由于它被广泛使用，并且具有快速开发应用程序的能力，在我看来值得一试。

不安全的代码也能在这里带来好处吗？

Answer 1

一种可能的优化是使用 BigInteger ModPow

它确实显着提高了性能。