盧卡斯萊默優化

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