Ich versuche, log zu berechnenab (und bekomme einen Fließkommawert zurück, keine ganze Zahl). Ich hatte vor, dies als zu tun log(b)/log(a). Mathematisch gesehen kann ich alle verwenden cmath log-Funktionen (Basis 2, e oder 10), um diese Berechnung durchzuführen; Ich werde diese Berechnung jedoch während meines Programms häufig ausführen, daher habe ich mich gefragt, ob eine von ihnen wesentlich schneller ist als die anderen (oder noch besser, ob es einen schnelleren, aber dennoch einfachen Weg gibt, dies zu tun). Wenn es darauf ankommt, sind sowohl a als auch b ganze Zahlen.
C/C++ schnellste Cmath-Protokolloperation
Lesezeit: 7 Minuten
12992800cookie-checkC/C++ schnellste Cmath-Protokolloperation
Nick
Mark Lösegeld
Erstmal vorrechnen 1.0/log(a) und jeweils multiplizieren log(b) stattdessen durch diesen Ausdruck.
Bearbeiten: Ich sagte ursprünglich, dass der natürliche Logarithmus (Basis e) am schnellsten wäre, aber andere geben an, dass die Basis 2 direkt vom Prozessor unterstützt wird und am schnellsten wäre. Ich habe keinen Grund, daran zu zweifeln.
Bearbeiten 2: Ich bin ursprünglich davon ausgegangen a war eine Konstante, aber beim erneuten Lesen der Frage, die nie gestellt wird. Wenn dies der Fall ist, würde eine Vorausberechnung keinen Nutzen bringen. Ist dies jedoch der Fall, können Sie die Lesbarkeit durch eine geeignete Wahl der Variablennamen erhalten:
const double base_a = 1.0 / log(a);
for (int b = 0; b < bazillions; ++b)
double result = log(b) * base_a;
Seltsamerweise liefert Microsoft keine Base-2-Log-Funktion mit, was erklärt, warum ich damit nicht vertraut war. Auch die x86-Anweisung zum Berechnen von Protokollen enthält automatisch eine Multiplikation, und die für die verschiedenen Basen benötigten Konstanten sind auch über eine verfügbar optimierter Unterrichtalso würde ich erwarten, dass die 3 verschiedenen Protokollfunktionen ein identisches Timing haben (sogar Basis 2 müsste mit 1 multipliziert werden).
-
+1 Schöne Beobachtung. Obwohl die andere Antwort einen Punkt hat, da diese Operationen sowieso so schnell sind, ist die Optimierung ein wenig viel.
– Jesus Ramos
11. Juli 2011 um 20:11 Uhr
-
Das stimmt, aber die Optimierung durch neuere Compiler beseitigt fast die Notwendigkeit, einige dieser Dinge zu tun, was irgendwie traurig ist. Obwohl die meisten Leute solche Optimierungen immer noch ausschreiben.
– Jesus Ramos
11. Juli 2011 um 20:14 Uhr
-
Ich bin mir ziemlich sicher, dass der Logarithmus zur Basis 2 der schnellste ist, da er der einzige ist, der einen eigenen Assembler-Befehl hat (zumindest im 8087-Befehlssatz).
– MartinStettner
11. Juli 2011 um 20:15 Uhr
-
@Markus: genau richtig. Es sei denn, eine Flagge wie
fast-mathgesetzt ist, kann der Compiler die Division nicht durch eine reziproke Multiplikation ersetzen (nicht nur, weil dadurch die Rundung geändert wird, sondern auch, weil es falsche Überläufe und NaNs verursachen kann). Und ja, teilen ist viel langsamer als die Multiplikation auf den meisten aktuellen Prozessoren.– Stefan Kanon
11. Juli 2011 um 20:56 Uhr
-
Es ist unwahrscheinlich, dass die Protokollanweisungen von modernen Compilern verwendet werden, da sie ungenau sind (im Vergleich zu dem, was Sie in der Software tun können) und nur im veralteten x87-Befehlssatz verfügbar sind.
– zol
30. Januar 2016 um 14:19 Uhr
Seit b und a Ganzzahlen sind, können Sie die ganze Herrlichkeit verwenden bisschen gefummelt um ihre Protokolle zur Basis 2 zu finden. Hier sind einige:
- Finden Sie die logarithmische Basis 2 einer ganzen Zahl mit dem MSB N in O (N) -Operationen (der offensichtliche Weg)
- Ermitteln Sie die ganzzahlige logarithmische Basis 2 einer Ganzzahl mit einem 64-Bit-IEEE-Float
- Finden Sie die logarithmische Basis 2 einer ganzen Zahl mit einer Nachschlagetabelle
- Ermitteln Sie die logarithmische Basis 2 einer N-Bit-Ganzzahl in O(lg(N))-Operationen
- Ermitteln Sie die logarithmische Basis 2 einer N-Bit-Ganzzahl in O(lg(N))-Operationen mit Multiplizieren und Nachschlagen
Ich überlasse es Ihnen, die beste “Fast-Log”-Funktion für Ihre Bedürfnisse auszuwählen.
-
Coole Verlinkung. Ich frage mich, ob eine dieser Methoden schneller ist als die einfachen auf modernen Prozessoren?
– Markieren Sie Lösegeld
11. Juli 2011 um 20:24 Uhr
-
@MarkRansom: Sie sind alle viel langsamer als die Verwendung einer Hardwareanweisung zum Zählen führender Nullen. die alle modernen Architekturen haben, da die Schleifenmethoden bei unterschiedlichen Eingaben eine Verzweigung falsch vorhersagen. Das hw inn ist sehr günstig. Das Original von x86
bsrist klobig (undefiniert, wenn Eingabe 0 ist), gibt aber das log2-Ergebnis direkt aus, anstatt 32-log2(a). Nur recht aktuelle CPUs unterstützenlzcntdie für definiert ist0. AVX512CD vorstellenVPLZCNTDwas dies für jedes Element in einem Vektor von ganzen Zahlen tut.– Peter Cordes
31. Januar 2016 um 4:29 Uhr
-
Außerdem dachte ich, das OP suche nach einer Lösung, die Zwischenergebnisse nicht auf Ganzzahlen rundet / abschneidet. Sicher, die Startwerte sind ganzzahlig, aber
integer_log2(uint32_t)hat nur einen Bereich von 0..32, also ergibt der Bruchteil a groß Unterschied. Es gibt eine riesige Auswahl an Zahlen zwischen 2^30 und 2^31, aber alle haben das gleiche ilog2.– Peter Cordes
31. Januar 2016 um 4:33 Uhr
Auf den Plattformen, für die ich Daten habe, log2 ist etwas schneller als die anderen, was meinen Erwartungen entspricht. Beachten Sie jedoch, dass der Unterschied ist äußerst gering (nur ein paar Prozent). Das ist wirklich keine Sorge wert.
Schreiben Sie eine klare Implementierung. Dann die Leistung messen.
Im 8087-Befehlssatz gibt es nur einen Befehl für den Logarithmus zur Basis 2, daher würde ich vermuten, dass dieser der schnellste ist.
Natürlich hängt diese Art von Frage weitgehend von Ihrem Prozessor / Ihrer Architektur ab, daher würde ich vorschlagen, einen einfachen Test zu machen und ihn zu timen.
Die Antwort ist:
- es hängt davon ab, ob
- profiliere es
Sie erwähnen nicht einmal Ihren CPU-Typ, den Variablentyp, die Compiler-Flags, das Datenlayout. Wenn Sie viele davon parallel ausführen müssen, bin ich sicher, dass es eine SIMD-Option geben wird. Ihr Compiler Wille Optimieren Sie das, solange Sie Ausrichtung verwenden und einfache Schleifen löschen (oder Valarray, wenn Sie archaische Ansätze mögen).
Wahrscheinlich hat der Intel-Compiler in diesem Bereich spezielle Tricks für Intel-Prozessoren.
Wenn Sie wirklich wollten, könnten Sie CUDA verwenden und die GPU nutzen.
Ich nehme an, wenn Sie das Pech haben, diese Befehlssätze zu vermissen Sie könnten auf der etwas fummeligen Ebene nach unten gehen und schreiben Sie einen Algorithmus, der macht eine schöne Annäherung. In diesem Fall kann ich mehr als einen Apfelkuchen darauf verwetten, dass 2-Log schneller sein wird als jedes andere Basis-Log
Mit den Worten von Donald Knuth: „Wir sollten kleine Effizienzen vergessen, sagen wir etwa 97 % der Zeit: Vorzeitige Optimierung ist die Wurzel allen Übels“
– Du
11. Juli 2011 um 20:09 Uhr
@Du „geistlose Mantras sind ein Gräuel für produktives Denken“
– Tamás Szelei
11. Juli 2011 um 20:15 Uhr
@You – Ich hatte immer das Gefühl, dass das Zitat überbeansprucht ist. Sicherlich gibt es Situationen, in denen Sie viel Aufwand betreiben, die Lesbarkeit des Codes verringern und am Ende den Unterschied nicht bemerken. Es gibt viele andere Fälle, in denen Sie sehr wenig Aufwand betreiben, die Lesbarkeit überhaupt nicht beeinträchtigen und eine enorme Verbesserung erzielen können. Zu wissen, welcher Fall welcher ist, kommt mit Übung, es sei denn, Sie hören ganz auf, die Aussicht zu berücksichtigen.
– Markieren Sie Lösegeld
11. Juli 2011 um 20:18 Uhr
@You: Multiplizieren, Addieren und Subtrahieren sind alle viel schneller als log, exp und trig. Sqrt und divide liegen dazwischen. (Intel Skylake hat eine sehr schnell FP teilen Einheit, aber es ist immer noch Faktor 8 schlechterer Durchsatz und Faktor ~3 schlechtere Latenz als FP mul. sqrt ist nur geringfügig langsamer). Es ist viel schneller, ein geometrisches Mittel als zu überprüfen
(x^2+y^2) < maxdistance^2Anstatt vonsqrt(x^2+y^2) < maxdistance, insb. wenn Sie diese Überprüfung wiederholt durchführen (wie in einer inneren Mandelbrot-Schleife) oder mit ganzen Zahlen. (Die x86-Skalar-Integer-Division ist langsamer als die SIMD-FP-Division.)– Peter Cordes
31. Januar 2016 um 4:16 Uhr
@You Das ist ein teilweises und in der Tat selektives Zitat. Ich schlage vor, Sie lesen den Rest, insbesondere den letzten Satz. Das vollständige Zitat lautet wie folgt: „Programmierer verschwenden enorm viel Zeit damit, über die Geschwindigkeit unkritischer Teile ihrer Programme nachzudenken oder sich darüber Gedanken zu machen, und diese Effizienzbemühungen wirken sich tatsächlich stark negativ aus, wenn Debugging und Wartung in Betracht gezogen werden. Wir sollten kleine Effizienzen vergessen, sagen wir etwa 97 % der Zeit: Vorzeitige Optimierung ist die Wurzel allen Übels. Dennoch sollten wir unsere Chancen in diesen kritischen 3 % nicht ungenutzt lassen.’
– Benutzer207421
31. Januar 2016 um 23:21 Uhr