Anzahl der FLOPs (Gleitkommaoperationen) zur Potenzierung

7

Wie viele Gleitkommaoperationen sind erforderlich, um eine Exponentiation durchzuführen (Potenz von)?

Angenommen, die Multiplikation von zwei Floats verwendet eine FLOP, die Anzahl der Operationen für xn wird sein n1. Gibt es jedoch einen schnelleren Weg, dies zu tun? Wie funktioniert es wennn ist keine ganze Zahl?

Herr Eivind
quelle

Antworten:

6

Angenommen, die Multiplikation zwischen zwei Zahlen verwendet eine FLOP, die Anzahl der Operationen für xn wird sein n1. Gibt es jedoch einen schnelleren Weg, dies zu tun ...

Es gibt mit Sicherheit einen schnelleren Weg, dies für nicht negative ganzzahlige Potenzen zu tun. Zum Beispiel,x14=x8x4x2. Die Berechnung erfordert eine Multiplikationx2, noch eine zu berechnen x4, noch eine zu berechnen x8und zwei weitere, um diese drei Zahlen zu multiplizieren. Dies legt einfache Kosten und einen einfachen Algorithmus nahe.

  • Wandeln Sie die nicht negative ganzzahlige Potenz in Basis 2 um.
  • Zählen Sie die Anzahl der Einsen in dieser Darstellung.
  • Addieren Sie die Zweierpotenz, die dem höchstwertigen Nicht-Null-Bit in dieser Darstellung entspricht.
  • Subtrahiere eins.

Dies ergibt einen präzisen Algorithmus für jede nicht negative ganzzahlige Leistung. Dieser Algorithmus ist der effizienteste bis zux14. Dieser Algorithmus schlägt vor, dass zur Berechnung sechs Multiplikationen erforderlich sindx15 schon seit x15=x8x4x2x. 15 ist jedoch 120 in Basis 3 und 30 in Basis 5, was beide impliziert, dass nur fünf Multiplikationen zur Berechnung benötigt werdenx15:: x15=(x3)4x3 von der Basis drei Darstellung, und x15=(x5)3von der Basis fünf Darstellung. Die minimale Anzahl von Multiplikationen, die zur Berechnung benötigt werdenxn wo nist eine nicht negative ganze Zahl ist in der Tat ein NP-vollständiges Problem . Aber es ist viel weniger alsn1 Multiplikationen.

... und wie funktioniert es wenn n ist keine ganze Zahl?

Es gibt einige Tricks, die man anwenden kann, wenn nist eine rationale. Doch wennx ist echt und nist ein nicht negativer Real, muss man auf Approximationstechniken zurückgreifen. (Zum Beispiel werden Approximationstechniken bei der Berechnung zweimal verwendetexp(nln(x)).)

David Hammen
quelle
Sind Sie sicher, die Anzahl der Multiplikationen zu berechnen, die in NP-complete benötigt werden? Dies scheint ein Problem zu sein, das von der Faktorisierung abhängt, von der angenommen wird, dass sie NP-Intermediate ist.
Stux
Haben Sie eine Referenz für die Komplexität von Additionsketten?
Yuval Filmus
@stux: Nur weil Faktorisierungen Kandidatenlösungen ergeben, bedeutet dies nicht, dass alle Lösungen auf Faktorisierung basieren ...
user21820
@ user21820: das ist sehr wahr, daher meine frage und formulierung. Wenn alle Lösungen durch Faktorisierung gesteuert werden, kann das Problem (höchstwahrscheinlich) nicht NP-vollständig sein. Ist dies nicht der Fall, enthält der bereitgestellte Link keine Referenz zum Nachweis der NP-Vollständigkeit.
Stux
2
@stux - Downey, Peter, Benton Leong und Ravi Sethi. "Berechnen von Sequenzen mit Additionsketten." SIAM Journal on Computing 10.3 (1981): 638-646.
David Hammen
5

Die Verwendung von n-1-Multiplikationen wäre ziemlich dumm. Wenn zum Beispiel n = 1024 ist, quadrieren Sie nur zehnmal. Der schlimmste Fall ist 2 * log_2 (n). In Donald Knuth, Kunst der Computerprogrammierung, finden Sie einige Details, wie Sie dies schneller tun können. Es gibt einige Situationen, wie n = 1023, in denen Sie x zehnmal quadrieren und x ^ 1024 geben und dann durch x dividieren würden.

gnasher729
quelle
Danke, ich weiß nicht, warum mir das nicht in den Sinn gekommen ist ...
Mr. Eivind
4

Sie können die Formel verwenden

xy=exp(ylnx).

Wenn Sie nur Multiplikationen verwenden möchten, wann nist eine natürliche Zahl, die Sie durch wiederholtes Quadrieren verwenden könnenO(logn)Multiplikationen. Für anderenMultiplikation allein reicht nicht aus.

Yuval Filmus
quelle
3

Die Leute haben dir gesagt, was wann passiert n ist eine ganze Zahl.

In Bezug auf, wenn es nicht, es kann nicht einmal existieren , einen Weg Floating-Point - Potenzierung überhaupt zu tun.

Es heißt Table-Maker's Dilemma und besagt, dass die benötigte Speichermenge unbegrenzt ist:

Es gibt keine allgemeine Möglichkeit, vorherzusagen, wie viele zusätzliche Ziffern getragen werden müssen, um einen transzendentalen Ausdruck zu berechnen und ihn korrekt auf eine vorab zugewiesene Anzahl von Ziffern zu runden.
Sogar die Tatsache (falls zutreffend), dass eine endliche Anzahl zusätzlicher Ziffern letztendlich ausreicht, kann ein tiefer Satz sein.

user541686
quelle
Für die Gleitkomma-Arithmetik ist es offensichtlich, dass eine endliche Anzahl zusätzlicher Ziffern ausreicht, da es eine endliche Menge von Eingaben gibt.
Gnasher729
@ gnasher729: Ja ... ich hätte dies nicht auf StackOverflow gepostet, aber da dies auf CS.SE war, war ich mir nicht sicher, wie ich das Wort "Gleitkomma" in der Frage wörtlich interpretieren sollte. Ich dachte, es gibt eine gute Chance, dass es nur als Synonym für "nicht ganzzahlig" verwendet wurde, also dachte ich, ich würde den transzendentalen Fall der Vollständigkeit halber erwähnen.
user541686
1
Möglicherweise eng damit verbunden ist die (frühere) außergewöhnliche Langsamkeit der früheren Implementierung der gcc-Mathematikbibliothek pow(x,y)für einige Eingaben . Es war sehr bemüht (wohl zu sehr bemüht), die schwer fassbare halbe ULP-Genauigkeit zu verfolgen.
David Hammen
0

Wenn Sie das Problem ernst nehmen, versuchen Sie möglicherweise nicht, eine Lösung mit der geringsten Anzahl von Multiplikationen, sondern mit der niedrigsten Ausführungszeit zu finden.

Stellen Sie sich ein Modell vor, bei dem Sie in jedem Zyklus eine Multiplikation starten können, aber jede Multiplikation eine feste Anzahl von Zyklen benötigt, z. B. 3 Zyklen. Eine Methode zur Berechnung von x ^ n mit k Multiplikationen kann 3k Zyklen dauern (wenn jede Multiplikation von einem Ergebnis abhängt, das kurz zuvor berechnet wurde), während eine Methode mit mehr Multiplikationen möglicherweise schneller ausgeführt wird.

Zum Beispiel: Um x ^ 15 zu berechnen, können Sie in dieser Reihenfolge x ^ 2 = x * x, x ^ 3 = (x ^ 2) * x, x ^ 6 = (x ^ 3) ^ 2, x ^ 7 berechnen = x ^ 6 * x, x ^ 14 = (x ^ 7) ^ 2, x ^ 15 = x ^ 14 * x. Sechs Multiplikationen, die jedoch jeweils von der vorherigen abhängen.

Oder Sie berechnen x ^ 2, x ^ 4 = (x ^ 2) ^ 2, x ^ 3 = x ^ 2 * x, x ^ 5 = (x ^ 4) * x, x ^ 15 = x ^ 5 * x ^ 3, Sie haben also nur vier Multiplikationen, abhängig von den vorherigen Ergebnissen.

gnasher729
quelle
Der letzte Absatz ist falsch. x5x3 ist x8nicht x15. Berechnenx15 erfordert mindestens fünf Multiplikationen (oder vier Multiplikationen, um zu ergeben x16, gefolgt von einer Teilung durch x, aber das ist teurer als fünf Multiplikationen).
David Hammen