Was ist schneller als Std :: Pow?

Question

Mein Programm gibt 90% der CPU-Zeit in der std::pow(double,int)-Funktion aus. Genauigkeit ist hier kein Hauptanliegen, also habe ich mich gefragt, ob es schnellere Alternativen gibt. Eine Sache, an die ich denken wollte, ist Gießen zu schweben, die Operation durchzuführen und dann zurück zu verdoppeln (habe das noch nicht versucht); Ich bin besorgt, dass dies nicht eine tragbare Art und Weise die Leistung zu verbessern (nicht die meisten CPUs auf Doppel arbeiten eigen sowieso?)

Prost

Answer 1

Es sieht aus wie Martin Ankerl einige Artikel zu diesem Thema hat, Optimized Approximative pow() in C/C++ ist ein und es verfügt über zwei schnelle Versionen, ist wie folgt:

inline double fastPow(double a, double b) { 
    union { 
    double d; 
    int x[2]; 
    } u = { a }; 
    u.x[1] = (int)(b * (u.x[1] - 1072632447) + 1072632447); 
    u.x[0] = 0; 
    return u.d; 
} 

, die auf Typ punning durch eine Vereinigung setzt die ist nicht definiertes Verhalten in C++, von dem Normentwurf Abschnitt 9.5[class.union]:

in einer Union, höchstens einer der nicht-statischen Datenelemente sein, kann ctive jederzeit, dh der Wert von meisten der nicht-statischen Daten Mitglieder können jederzeit in einer Union gespeichert werden. [...]

aber die meisten Compiler einschließlich gcc support this with well defined behavior:

Die Praxis von einem anderen Gewerkschaftsmitglied des Lesens als die zuletzt geschrieben (so genannten „Typ-punning“) ist weit verbreitet. Auch bei -fstrict-Aliasing, Typ-punning zulässig, sofern der Speicher durch die Vereinigung Typ zugegriffen wird

aber das ist nicht universell wie this article points out und wie ich point out in my answer herememcpy verwenden, sollten identischen Code erzeugen und nicht undefiniert nicht aufrufen Verhalten.

Er verbindet sich auch mit einem zweiten Optimized pow() approximation for Java, C/C++, and C#.

Der erste Artikel auch Links zu seinem Microbenchmarks here

Answer 2

Je nachdem, was Sie tun müssen, in der Log-Domäne arbeitet funktionieren könnte Das heißt, Sie ersetzen alle Ihre Werte durch ihre Logarithmen. Multiplikation wird Addition, Division wird Subtraktion und Potenzierung wird Multiplikation. Aber jetzt Addition und Subtraktion werden teuer und etwas fehleranfällige Operationen.

Answer 3

Wie groß sind Ihre Zahlen? Sind sie zur Kompilierzeit bekannt? Es ist viel besser, x^2 als x*x im Gegensatz zu pow(x,2) zu berechnen. Hinweis: Fast alle Anwendungen von pow() zu einer ganzzahligen Potenz beinhalten das Erhöhen einer Zahl auf die zweite oder dritte Potenz (oder die multiplikative Inverse bei negativen Exponenten). Die Verwendung von pow() ist in solchen Fällen übertrieben. Verwenden Sie eine Vorlage für diese kleinen ganzzahligen Potenzen oder verwenden Sie einfach x*x.

Wenn die Ganzzahlen klein sind, aber zur Kompilierzeit nicht bekannt sind, sagen wir zwischen -12 und +12, wird die Multiplikation immer noch pow() schlagen und die Genauigkeit nicht verlieren. Sie benötigen keine elf Multiplikationen, um x^12 zu berechnen. Vier werden es tun. Verwenden Sie die Tatsache, dass x^(2n) = (x^n)^2 und x^(2n + 1) = x * ((x^n)^2). Zum Beispiel ist x^12 ((x * x * x)^2)^2.Zwei Multiplikationen zur Berechnung von x^3 (x * x * x), eine weitere zur Berechnung von x^6 und eine letzte zur Berechnung von x^12.