Was ist die numerische Stabilität von std :: pow() im Vergleich zur iterierten Multiplikation?

Question

Welche Art von Stabilitätsproblemen treten auf oder werden gelöst, indem std::pow() verwendet wird?

• Wird es stabiler sein (oder schneller oder überhaupt anders) im Allgemeinen eine einfache Funktion zu implementieren log(n) iteriert vervielfacht auszuführen, wenn der Exponent bekannt ist, eine ganze Zahl zu sein?

• Wie vergleicht std::sqrt(x), Stabilität, zu etwas von der Form std::pow(x, k/2)? Wäre es sinnvoll, die bevorzugte Methode zu wählen, um auf eine ganzzahlige Potenz zu erhöhen, und dann in einer Quadratwurzel zu multiplizieren, oder sollte ich annehmen, dass std::pow() schnell und präzise ist, um die Präzision der Maschine zu verbessern? Wenn k = 1, gibt es einen Unterschied von std::sqrt()?

• Wie würde std::pow(x, k/2) oder die obige Methode stabilitätsmäßig mit einer ganzzahligen Exponentiation von std::sqrt(x) verglichen?

Und als Bonus, was sind die Geschwindigkeitsunterschiede wahrscheinlich?

Answer 1

Wird es im Allgemeinen stabiler (oder schneller oder überhaupt anders) sein, eine einfache Funktion zum Ausführen von log (n) iterierten Multiplikationen zu implementieren, wenn der Exponent bekanntermaßen eine ganze Zahl ist?

Das Ergebnis exponentiation by squaring für ganzzahlige Exponenten ist im allgemeinen weniger genau als pow, aber beide sind in dem Sinne stabil, dass eine enge Eingänge Schließen Ergebnisse. Sie können eine Potenzierung durch Quadrieren erwarten, um 0,5 ULP des relativen Fehlers durch Multiplikation einzuführen (z. B. 1 ULP des Fehlers für die Berechnung x als x * x * x). Wenn das zweite Argument n statisch als 2 bekannt ist, dann implementieren Sie x ⁿ als x * x. In diesem Fall ist es schneller und genauer als jede mögliche Alternative.

Wie std :: sqrt (x) vergleichen, Stabilität weist, um etwas von der Form std :: pow (x, k/2)

Erstens kann die Genauigkeit von sqrt nicht Für eine IEEE-754-Implementierung muss man sich überlegen, denn sqrt ist eine der grundlegenden Operationen, die dieser Standard so genau wie möglich vorgibt.

Aber Sie fragen nicht über sqrt, Sie fragen (glaube ich) über < Berechnung von x ⁿ> * sqrt (x) in Bezug auf pow(x, n + 0.5) gegenüber. Für eine Qualitätsimplementierung von pow können Sie wiederum erwarten, dass pow(x, n + 0.5) genauer ist als die Alternativen. Obwohl sqrt(x) zu 0,5 ULP berechnet werden würde, führt die Multiplikation ihre eigene Annäherung von bis zu 0,5 ULP ein, und alles in allem ist es besser, das Ergebnis, an dem Sie interessiert sind, in einem einzigen Aufruf einer gut implementierten Funktion zu erhalten. Eine Qualitätsimplementierung von pow gibt Ihnen 1 ULP der Genauigkeit für sein Ergebnis, und die besten Implementierungen werden 0,5 ULP "garantieren".

Und als Bonus, was sind die Geschwindigkeitsunterschiede wahrscheinlich?

Wenn Sie im Voraus wissen, dass der Exponent eine kleine ganze Zahl oder mehr von 0,5 sein wird, dann haben Sie Informationen, die der Implementierer von pow nicht hatte, so können Sie sie durch zumindest die Kosten für schlagen der Test, um zu bestimmen, dass das zweite Argument eine kleine ganze Zahl ist. Außerdem strebt der Implementierer einer Qualitätsimplementierung ein genaueres Ergebnis an als die einfache Potenzierung durch Quadrieren. Auf der anderen Seite kann der Implementierer von pow äußerst komplizierte Techniken verwenden, um die durchschnittliche Ausführungszeit trotz der besseren Genauigkeit zu minimieren: siehe beispielsweise CRlibm's implementation. Ich setze das Verb "Garantie" oben in Anführungszeichen, wenn ich über die besten Implementierungen von pow spreche, weil pow eine Funktion ist, für die CRlibms 0,5 ULP Genauigkeitsgarantie only “with astronomical probability” ist.