2013-05-10 11 views
6

Ich habe daran gearbeitet, den Lucas-Lehmer-Primalitätstest mit C# -Code zu optimieren (ja, ich mache etwas mit Mersenne-Primzahlen, um perfekte Zahlen zu berechnen. Ich habe mich gefragt, ob es mit dem aktuellen Code noch weiter geht . Verbesserungen in der Geschwindigkeit ich die System.Numerics.BigInteger-Klasse verwenden, um die Zahlen zu halten, ist es vielleicht nicht die klügste, werden wir es dann sehenLucas Lehmer Optimierung

Dieser Code tatsächlich auf der Intelligenz basiert auf gefunden. http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test

Auf dieser Seite (im Zeitstempel) gibt es einige Nachweise, um die Teilung zu optimieren

Der Code für die LucasTest ist:

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

}

Edit: , die schneller als die Verwendung von ModPow aus der BigInteger Klasse ist, wie durch Mare Infinitus unten vorgeschlagen. Dass die Umsetzung ist:

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

}

Die LucasLehmerMod Verfahren wie folgt durchgeführt wird:

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

Was ich fürchte, ist, dass bei der Verwendung der BigInteger-Klasse aus dem .NET-Framework, ich bin an ihre Berechnungen gebunden. Würde es bedeuten, dass ich meine eigene BigInteger-Klasse erstellen muss, um sie zu verbessern? Oder kann ich unterstützen, indem ein KaratsubaSquare mit (abgeleitet vom Karatsuba-Algorithmus) wie dieses, was ich auf Optimizing Karatsuba Implementation gefunden:

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

Also im Grunde möchte ich sehen, ob es möglich ist, die Lucas-Lehmer-Testverfahren zur Verbesserung der durch Optimierung der for-Schleife. Allerdings stecke ich da ein bisschen fest ... Ist es überhaupt möglich?

Alle Gedanken sind natürlich willkommen.

Einige zusätzliche thoughs:

ich mehrere Threads beschleunigen die Berechnung auf der Suche nach Perfekte Zahlen nutzen könnten. Ich habe jedoch (noch) keine Erfahrung mit einer guten Partitionierung. Ich werde versuchen, meine Gedanken zu erklären (noch kein Code):

Zuerst werde ich eine primetable mit Verwendung des Siebs von Erathostenes erzeugen. Es dauert etwa 25 ms, um Primzahlen im Bereich von 2 - 1 Million Einzelfäden zu finden.

Was C# bietet, ist ziemlich erstaunlich. Unter Verwendung von PLINQ mit der Parallel.For-Methode könnte ich mehrere Berechnungen fast gleichzeitig ausführen, jedoch teilt es das primeTable-Array in Teile auf, die für die Suche nicht respektiert werden.

Ich habe bereits herausgefunden, dass der automatische Lastausgleich der Threads für diese Aufgabe nicht ausreicht. Daher muss ich einen anderen Ansatz versuchen, indem ich die Lastverteilung in Abhängigkeit von den Mersenne-Zahlen dividiere, um eine perfekte Zahl zu finden und zu verwenden. Hat jemand Erfahrung damit? Diese Seite scheint mir ein wenig hilfreich zu sein: http://www.drdobbs.com/windows/custom-parallel-partitioning-with-net-4/224600406

Ich werde mich weiter damit befassen.

Im Moment sind meine Ergebnisse wie folgt. Mein aktueller Algorithmus (unter Verwendung der Standardklasse BigInteger von C#) kann die ersten 17 perfekten Zahlen (siehe http://en.wikipedia.org/wiki/List_of_perfect_numbers) innerhalb von 5 Sekunden auf meinem Laptop finden (ein Intel I5 mit 4 Kernen und 8 GB RAM). Aber dann bleibt es stecken und findet nichts innerhalb von 10 Minuten.

Das kann ich noch nicht ... Mein Bauchgefühl (und gesunder Menschenverstand) sagt mir, dass ich in den LucasLehmer-Test schauen sollte, da ein For-Loop die 18. perfekte Zahl (mit Mersenne Prime 3217) berechnen würde 3214 mal laufen lassen. Es gibt Raum für Verbesserungen, die ich denke ...

Was Dinony posted unten ist ein Vorschlag, es vollständig in C zu schreiben. Ich stimme zu, dass würde meine Leistung steigern, aber ich C#, um herauszufinden, es ist Einschränkungen und Vorteile. Da es weit verbreitet ist und seine Fähigkeit, Anwendungen schnell zu entwickeln, schien es mir wert, es zu versuchen.

Können unsichere Codes auch hier Vorteile bieten?

+1

Haben Sie wirklich die BigInteger hier brauchen? Und wenn du das mit Ja antwortest, ist 'ModPow' vielleicht dein Freund. –

+0

Mare Infinitus, das könnte interessant sein. Ja, ich brauche einen BigInteger, da die perfekten Zahlen dazu neigen, ziemlich groß zu werden ... Die 17. perfekte Zahl besteht aus 1373 Ziffern. Ich werde sehen, was ich mit ModPow machen kann! – RvdV79

+0

Ich habe vor einigen Jahren einen Test geschrieben, aber in C# und mit BigInteger. Der ModPow hat definitiv den Unterschied gemacht. Denken Sie, es war für das Projekt Euler. Die Frage ist: Brauchen Sie diesen speziellen Algorithmus oder nur einen, der die Aufgabe erfüllt? –

Antwort

2

Eine mögliche Optimierung ist BigInteger ModPow

verwenden Es erhöht wirklich die Leistung erheblich .

+0

Mare Infinitus, Ich habe Ihren früheren Vorschlag in meinem ursprünglichen Beitrag aktualisiert. Implementieren und Verwenden von ModPow ist eigentlich langsamer als meine Optimierung, die Divisionen entfernt ... Allerdings plus eins für den Vorschlag! – RvdV79

+0

Ich habe Ihre Antwort bisher akzeptiert. Es ist der beste Vorschlag beim Testen von Primzahlen vor dem Eintritt in den Lucas Lehmer-Test! – RvdV79

1

Wie wäre es mit der Anpassung des Codes an C? Ich habe keine Ahnung von den Algorithmus, aber es ist nicht so viel Code .. so die größte Laufzeitverbesserung C werden die Anpassung könnte

+0

Ja, das scheint auch nicht zu schwierig zu sein. Nicht viel Infrastruktur, die C# einfacher macht als C. –

+0

Dem kann ich völlig zustimmen. @dinony. Allerdings hatte ich das Gefühl, es in C# zu programmieren. Wenn das die wahre Optimierung ist (an der ich überhaupt nicht zweifle), muss ich weiter schauen. Irgendwie muss es möglich sein, den Algorithmus zu beschleunigen. Ich bemerkte auch, dass die Karatsuba könnte etwas effizienter mit Bitmasken implementiert werden. – RvdV79

+0

Yap Ich weiß, Programmierung in C# ist wirklich verlockend und macht Spaß, aber wenn ich Optimierung höre, denke ich C/C++ :) ..Ich weiß, es ist nicht die Antwort, die Sie wollten, vielleicht kann jemand, der den Algorithmus kennt, Ihnen C# Optimierungshinweise geben – dinony

2

Nur eine Notiz für Infos ... In Python, diese

ss = KaratsubaSquare(ss) - 2 

hat schlechtere Leistung als das:

ss = ss*ss - 2 
+1

Wenn irgendeine Bibliothek große Integer-Operationen implementiert, dann würde ich annehmen, dass dies auf die schnellstmögliche Weise geschieht. Daher wird Python entweder die Karatsuba-Methode selbst verwenden, aber hoch optimiert und abgestimmt, oder es werden schnellere Methoden wie die Verallgemeinerung der Karatsuba-Methode oder FFT-Methoden verwendet. – gnasher729