Lucas Lehmer优化

Question

我一直在使用C#代码优化Lucas-Lehmer素数测试(是的，我正在使用Mersenne素数来计算完美数。我想知道用当前的代码是否有可能在速度上做进一步的改进。我使用System.Numerics.BigInteger类来保存数字，也许这不是最明智的，到时候我们会看到的。

这段代码实际上是基于以下测试上的智能

这一页(在时间戳)部分，给出了一些优化分割的证明。

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;
  }

}

编辑：，它比使用来自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);
}

我担心的是，当使用来自BigInteger框架的.NET类时，我被绑定到它们的计算中。这是否意味着我必须创建自己的BigInteger类来改进它？或者我可以通过使用KaratsubaSquare (从Karatsuba算法派生出来)来支持，就像我在优化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测试方法。不过，我被困在那里了.有可能吗？

当然，任何想法都是欢迎的。

一些额外的思想：

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

首先，我将用Erathostenes的筛子生成一个最原始的。它需要大约25毫秒来寻找素数范围内的2100万单螺纹.

C#提供的内容非常令人吃惊。使用PLINQ和Parallel.For方法，我几乎可以同时运行几个计算，但是，它将primeTable数组分割成不受搜索尊重的部分。

我已经发现线程的自动负载平衡不足以完成这项任务。因此，我需要尝试一种不同的方法，根据要查找的mersenne数来除以负载平衡，并使用它来计算一个完美的数字。有人对此有什么经验吗？这个页面似乎有点帮助：http://www.drdobbs.com/windows/custom-parallel-partitioning-with-net-4/224600406

我会进一步调查的。

目前，我的结果如下。我目前的算法(使用来自C#的标准C#类)可以在5秒内在我的笔记本电脑(一个带有4核和8GB内存的英特尔I5 )上找到前17个完美数字(参见数字)。然而，它会被卡住，10分钟内什么也找不到。

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

迪诺尼在下面发布的建议是在C中完全重写它，我同意这将提高我的性能，但是我选择C#来找出它的局限性和好处。由于它被广泛使用，而且它能够快速开发应用程序，在我看来，这是值得一试的。

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

Answer 1

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

它确实显着地提高了性能。

Answer 2

只是一张纸条.在蟒蛇里，这个

ss = KaratsubaSquare(ss) - 2

有比这更糟糕的表现：

ss = ss*ss - 2

Answer 3

如何将代码改编成C呢？我对算法一无所知，但代码不多..因此，最大的运行时改进可能是适应C。