我一直在努力使用 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 的筛子生成一个primtable。在 2 - 100 万个单线程范围内找到素数大约需要 25 毫秒。
C# 提供的功能非常惊人。将 PLINQ 与 Parallel.For 方法一起使用，我几乎可以同时运行多个计算，但是，它将 primeTable 数组分块为搜索不考虑的部分。
我已经发现线程的自动负载平衡不足以完成这项任务。因此，我需要尝试一种不同的方法，通过根据梅森数划分负载平衡来找到并使用它来计算完美数。有没有人有这方面的经验？这个页面似乎有点帮助：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 个完美数的 for 循环（使用 Mersenne Prime 3217）将运行 3214 次。估计还有改进的余地...
Dinony 在下面发布的建议是用 C 完全重写它。我同意这会提高我的性能，但是我选择 C# 来找出它的局限性和好处。由于它被广泛使用，而且它能够快速开发应用程序，我觉得它值得一试。
不安全的代码在这里也能带来好处吗？