Bedingte Tests in Primality durch Trial Division
Meine Frage betrifft den bedingten Test in der Testabteilung. Es scheint eine Debatte darüber zu geben, welchen konditionellen Test zu verwenden ist. Schauen wir uns den Code dafür von RosettaCode an.
%Vor%Die Radfaktorisierung oder die Verwendung einer vorgegebenen Liste von Primzahlen ändert nichts am Wesen meiner Frage.
Es gibt drei Fälle, an die ich denken kann, um den bedingten Test durchzuführen:
- p & lt; = n / p
- p * p & lt; = n
- int Schnitt = sqrt (n); für (p = 3; p & lt; = cut; p + = 2)
Fall 1: funktioniert für alle n, aber es muss bei jeder Iteration eine extra Division machen ( edit: eigentlich braucht es keine extra Division aber es ist noch langsamer. Ich bin mir nicht sicher warum. Siehe die Assembly-Ausgabe unten) . Ich habe herausgefunden, dass es doppelt so langsam ist wie Fall 2 für große Werte von n, die prim sind (auf meinem Sandy-Bridge-System).
Fall 2: ist wesentlich schneller als Fall 1, aber es hat ein Problem, dass es für große n überläuft und in eine Infinitivschleife geht. Der maximal zulässige Wert ist
%Vor%Beispiel für uint64_t wird Fall 2 in eine Endlosschleife für x = -1L-58 (x ^ 64-59) gehen, die eine Primzahl ist.
Fall 3: Es muss keine Division oder Multiplikation bei jeder Iteration gemacht werden, und es wird nicht wie Fall 2 überlaufen. Es ist auch etwas schneller als Fall 2. Die einzige Frage ist, ob sqrt (n) genau genug ist .
Kann mir jemand erklären, warum Fall 2 so viel schneller ist als Fall 1? Fall 1 benutzt KEINE zusätzliche Division wie ich, aber trotzdem ist es immer noch viel langsamer.
Hier sind die Zeiten für die Primzahl 2 ^ 56-5;
%Vor%Hier ist der Code, den ich verwendet habe, um Ссылка zu testen. Ich habe auch die Funktionen am Ende dieser Frage hinzugefügt.
Hier ist die Assembly-Ausgabe von GCC 4.8 mit -O3 für Fall 1 und Fall 2. Beide haben nur eine Division. Fall 2 hat auch eine Multiplikation, so ist meine erste Schätzung, dass Fall 2 langsamer wäre, aber es ist ungefähr zweimal so schnell auf GCC und MSVC. Ich weiß nicht warum.
Fall 1:
%Vor%Fall 2:
%Vor%Hier sind die Funktionen, die ich verwende, um die Zeit zu testen:
%Vor%Inhalt nach der Bounty hinzugefügt.
Aean entdeckte, dass im Fall 1 der Quotient genauso wie der Rest genauso schnell (oder etwas schneller) gespeichert wird als in Fall 2. Lassen Sie uns diesen Fall 4 aufrufen. Der folgende Code ist doppelt so schnell wie in Fall 1.
%Vor% Ich bin mir nicht sicher, warum das hilft. In jedem Fall muss Fall 2 nicht mehr verwendet werden. Für Fall 3 erhalten die meisten Versionen der Funktion sqrt in Hardware oder Software die richtigen Quadrate, so dass sie im Allgemeinen sicher verwendet werden können. Fall 3 ist der einzige Fall, der mit OpenMP funktioniert.
4 Antworten
UPD: Dies ist offensichtlich ein Problem mit der Optimierung des Compilers. Während MinGW nur eine div Anweisung im Schleifenkörper verwendete, konnten sowohl GCC unter Linux als auch MSVC den Quotienten aus der vorherigen Iteration nicht wiederverwenden.
Ich denke, das Beste, was wir tun könnten, ist quo und rem explizit zu definieren und sie im selben Basis-Anweisungsblock zu berechnen, um den Compiler anzuzeigen, den wir sowohl Quotienten als auch Rest haben wollen.
Ich habe Ihren Code aus Ссылка auf einem MinGW-w64-Compiler versucht, case 1 ist schneller als case 2 .
Also rate Sie kompilieren zielgerichtet auf eine 32-Bit-Architektur und verwenden uint64_t type. Ihre Assembly zeigt, dass sie kein 64-Bit-Register verwendet.
Wenn ich es richtig verstanden habe, gibt es den Grund.
In einer 32-Bit-Architektur werden 64-Bit-Zahlen in zwei 32-Bit-Registern dargestellt, Ihr Compiler übernimmt alle Verkettungsarbeiten. Es ist einfach, 64-Bit-Addition, Subtraktion und Multiplikation durchzuführen. Aber Modulo und Division wird durch einen kleinen Funktionsaufruf erledigt, der als ___umoddi3 und ___udivdi3 in GCC, aullrem und aulldiv in MSVC genannt wird.
Sie benötigen also für jede Iteration in ___umoddi3 , eine ___udivdi3 und eine Verkettung der 64-Bit-Multiplikation in case 1 eine ___udivdi3 und eine case 2 . Deshalb scheint case 1 in Ihrem Test doppelt so langsam zu sein wie case 2 .
Was Sie wirklich in case 1 bekommen:
Was Sie wirklich in case 2 bekommen:
MSVC konnte das Ergebnis von div nicht erneut verwenden. Die Optimierung wird durch return unterbrochen.
Probieren Sie diesen Code aus:
Das is_prime_B wird zweimal langsamer als is_prime_A auf MSVC / ICC für Windows.
sqrt(n) ist genau genug, solange Ihr sqrt monoton ansteigt, es erhält perfekte Quadrate richtig, und jedes unsigned int kann genau als double dargestellt werden. Alle drei sind auf jeder Plattform, die ich kenne, der Fall.
Sie können diese Probleme umgehen (wenn Sie sie für problematisch halten), indem Sie eine Funktion unsigned int sqrti(unsigned int n) implementieren, die das Quadrat der Quadratwurzel eines unsigned int mit Newtons Methode zurückgibt. (Dies ist eine interessante Übung, wenn Sie es noch nie zuvor gemacht haben!)
Über Ihre erste Frage: Warum (2) ist schneller als (1)?
Nun, das hängt vielleicht vom Compiler ab.
Im Allgemeinen könnte man jedoch erwarten, dass eine Division eine teurere Operation als eine Multiplikation ist.
Über Ihre zweite Frage: Ist sqrt () eine genaue Funktion?
Im Allgemeinen ist es korrekt.
Der einzige Fall, der Ihnen Probleme bereiten könnte, ist der, dass sqrt(n) eine ganze Zahl ist.
Zum Beispiel, wenn n == 9 und sqrt(n) == 2.9999999999999 in Ihrem System, dann sind Sie in Schwierigkeiten, da der ganzzahlige Teil 2 ist, aber der genaue Wert ist 3.
Diese seltenen Fälle können jedoch leicht behandelt werden, indem man eine nicht so kleine doppelte Konstante wie etwa 0,1 hinzufügt
So können Sie schreiben:
Der hinzugefügte Term 0.1 könnte Ihrem Algorithmus eine Iteration hinzufügen, was überhaupt kein großes Problem darstellt.
Schließlich ist die offensichtliche Wahl für Ihren Algorithmus (3), das heißt, die sqrt() -Ansatz, weil es keine Berechnung (Multiplikationen oder Divisionen) gibt, und der Wert stop wird nur einmal berechnet.
Eine weitere Verbesserung, die Sie haben können, ist die folgende:
- Beachten Sie, dass jede Primzahl
p >= 5die Form6n - 1oder well6n + 1hat.
Sie können also die Inkremente der Variablen d mit 2, 4, 2, 4 usw. abwechseln.
Tags und Links c math floating-point primes