Lucas Lehmer优化

Question

我一直在努力使用C#代码优化Lucas-Lehmer素性测试(是的,我正在使用Mersenne primes来计算完美数字.我想知道当前代码可以进一步提高速度.我使用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算法)来维持,我在优化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测试方法.但是,我有点卡在那里......它甚至可能吗？

当然欢迎任何想法.

一些额外的:

我可以使用多个线程来加速查找Perfect数字的计算.但是,我还没有很好的分区经验.我会试着解释一下我的想法(还没有代码):

首先,我将使用Erathostenes的筛子生成一个黄金表.在大约2到100万个单线程范围内找到质数大约需要25毫秒.

C#提供的内容非常令人惊讶.使用PLINQ和Parallel.For方法,我几乎可以同时运行几个计算,但是,它将primeTable数组分块为不符合搜索范围的部分.

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

我会进一步研究它.

至于现在,我的结果如下.我目前的算法(使用C#中的标准BigInteger类)可以在我的笔记本电脑上找到前17个完美数字(请参阅http://en.wikipedia.org/wiki/List_of_perfect_numbers)(一个4核和8GB的Intel I5) RAM).然而,它会卡住并在10分钟内找不到任何东西.

这是我无法比拟的......我的直觉(和常识)告诉我,我应该查看LucasLehmer测试,因为计算第18个完美数字的for循环(使用Mersenne Prime 3217)将运行3214次.我猜还有改进的余地......

Dinony在下面发布的建议是完全用C语言重写它.我同意这会提高我的表现,但是我选择C#来发现它的局限性和好处.由于它被广泛使用,并且它能够快速开发应用程序,因此我觉得值得尝试.

不安全的代码也可以在这里提供好处吗？

Answer 1

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

它确实显着提高了性能。