卢卡斯莱默优化

Question

我一直使用C＃代码（是的，我正在做与梅森素数的东西来计算完美的数字优化卢卡斯 - 莱默检验法。我想知道这是可能与当前的代码，以进一步使在速度提升我使用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; 
    } 

}

编辑： 哪个比使用从BigInteger类ModPow通过下面Mare的无限极所建议的速度更快。这实现：

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 Framework中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循环。但是，我有点卡在那里...甚至有可能吗？

当然欢迎任何想法。

一些额外的几点思考：

我可以使用多个线程来加快在寻找完美的数量计算。但是，我还没有经验（尚未）具有良好的分区。 我会尽力解释我的想法（无代码）：

首先，我将使用Erathostenes筛子生成一个可视表。大约需要25毫秒才能找到2-100万单线程范围内的素数。

＃提供了什么C是相当惊人的。与Parallel.For方法一起使用PLINQ，我可以几乎同时运行几个计算，但是，它会将primeTable数组分割成不受搜索限制的部分。

我已经想通了，线程的自动负载均衡是不够的这项任务。因此，我需要尝试一种不同的方法，通过根据mersenne数字划分负载平衡来找到并使用它来计算完美数字。有没有人有这方面的经验？本页面似乎有点帮助：http://www.drdobbs.com/windows/custom-parallel-partitioning-with-net-4/224600406

我会寻找到它进一步。

至于现在，我的结果如下。 我现在的算法（使用C＃中的标准BigInteger类）可以在我的笔记本电脑（具有4个内核和8GB内存的Intel I5）的5秒钟内找到前17个完美数字（请参见http://en.wikipedia.org/wiki/List_of_perfect_numbers）。但是，它会在10分钟内卡住并且找不到任何东西。

这是我无法比拟的东西......我的直觉（和常识）告诉我，我应该研究LucasLehmer测试，因为计算第18个完美数字（使用Mersenne Prime 3217）的for-loop会运行3214次。我猜...

Dinony在下面发布的是一个建议，用C完全重写它。我同意这会提高我的性能，但是我选择C＃来找出它的局限性和优点。由于它被广泛使用，并且能够快速开发应用程序，所以我觉得值得尝试。

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

Answer 1

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

这真的显著提高性能。

Answer 2

如何将代码调整为C？我不知道该算法的想法，但它不是多的代码..所以最大的运行时间改善，可以适应C.

Answer 3

只是记下信息... 在Python中，这

ss = KaratsubaSquare(ss) - 2 

有比这更糟糕的表现：

ss = ss*ss - 2