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?
Haben Sie wirklich die BigInteger hier brauchen? Und wenn du das mit Ja antwortest, ist 'ModPow' vielleicht dein Freund. –
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
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? –