Ich frage mich, ob eine schnelle Implementierung von pow (), zum Beispiel this one , ist ein schneller Weg, um die Wurzel einer ganzen Zahl als schnell sqrt (x) zu erhalten. Das wissen wir.
%Vor%Ich kann die Geschwindigkeit nicht selbst testen, weil ich keine schnelle Implementierung von sqrt gefunden habe. Meine Frage ist: Ist schnelle Implementierung von pow (x, 0.5f) schneller als schnelle sqrt (x)?
Edit: Ich meinte powf - pow, der floats im Doppelpack nimmt. (Doppel ist irreführender)
In Bezug auf die C-Standardbibliothek sqrt und pow lautet die Antwort nein .
Erstens, wenn pow(x, .5f) schneller als eine Implementierung von sqrt(x) wäre, würde der Ingenieur, der sqrt verwaltet, die Implementierung durch pow(x, .5f) ersetzen.
Zweitens werden Implementierungen von sqrt in kommerziellen Bibliotheken typischerweise speziell zur Ausführung dieser Aufgabe optimiert, oft von Leuten, die über das Schreiben von Hochleistungssoftware Bescheid wissen und in Assemblersprache oder in der Nähe schreiben, um die bestmögliche Leistung vom Prozessor zu erhalten.
Drittens haben viele Prozessoren Anweisungen, um sqrt auszuführen oder bei der Berechnung zu helfen. (Üblicherweise gibt es eine Anweisung, eine Schätzung des Reziprokwerts der Quadratwurzel und eine Anweisung zur Verfeinerung dieser Schätzung bereitzustellen.)
Der Code, den Sie verlinkt haben, / die Frage, die Sie gestellt haben, handelt davon, eine grobe Annäherung von sqrt unter Verwendung eines grob approximierten pow zu versuchen.
Ich habe die endgültige Version der pow-Näherungsroutine, auf die in der Frage Bezug genommen wurde, in C umgewandelt und die Laufzeit davon gemessen, als pow(3, .5) berechnet wurde. Ich habe auch die Laufzeit des Systems (Mac OS X 10.8) pow und sqrt und der die sqrt Approximation hier gemessen ( mit einer Iteration und Multiplikation mit dem Argument am Ende, um die Quadratwurzel zu erhalten, anstatt ihre Inverse).
Zuerst die berechneten Ergebnisse: Die pow-Näherung gibt 1.72101 zurück. Die sqrt-Approximation gibt 1.73054 zurück. Der korrekte Wert, der vom System pow und sqrt zurückgegeben wird, ist 1,73205.
Im 64-Bit-Modus auf einem MacPro4,1 dauert die pow-Approximation etwa 6 Zyklen, der Systempow-Vorgang dauert 29 Zyklen, die Quadratwurzel-Approximation dauert 10 Zyklen und das System-sqrt dauert 29 Zyklen. Diese Zeiten können einen gewissen Mehraufwand für das Laden von Argumenten und das Speichern von Ergebnissen enthalten (ich habe flüchtige Variablen verwendet, um den Compiler zu zwingen, nicht nutzlose Schleifeniterationen zu optimieren, so dass ich sie messen konnte).
(Diese Zeiten sind "effektive Durchsatz", in der Tat die Anzahl der CPU-Zyklen von einem Aufruf zu einem anderen beginnt.)
Ergebnisse, die den folgenden Code unter MSVC ++ 2013 64-Bit-Modus ausführen, vollständige Optimierung. ~ 9X Leistung für sqrt ();
Entfernung ist 2619435809228.278300
Pow () abgelaufene Zeit war 18413.000000 Millisekunden
Entfernung ist 2619435809228.278300
Sqrt () abgelaufene Zeit war 2002.000000 Millisekunden
%Vor%Kein Handwringen, Theoretisieren oder Pontification erforderlich. Schreiben Sie einfach den Benchmark und beobachten Sie das Ergebnis.
Im Allgemeinen kann ein spezifischeres Problem bei gleichen Fehlerbedingungen besser optimiert werden als ein allgemeineres Problem.
Daher könntest du diesen Algorithmus nehmen und b durch die Konstante 0.5 ersetzen, und jetzt hast du ein sqrt (), das mindestens so schnell wie pow () ist. Jetzt, da es konstant ist, kann der Compiler (oder ein Mensch) darauf basierend Optimierungen vornehmen.
Bitte beachten Sie, dass diese Funktion pow () eine Näherung ist und einen (relativ) großen Fehler hat und daher nicht annähernd so genau ist wie die meisten Bibliotheksfunktionen. Wenn Sie Ihre Implementierung von sqrt auf die gleichen Grenzen der Annäherung entspannen, könnten Sie es tatsächlich mindestens so schnell machen.
Tags und Links c math c++ performance