Angenommen, die Multiplikation zwischen zwei Zahlen verwendet eine FLOP, die Anzahl der Operationen für xn wird sein n−1. 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 alsn−1 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)).)
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.
quelle
Sie können die Formel verwendenxy=exp(ylnx).
Wenn Sie nur Multiplikationen verwenden möchten, wannn ist eine natürliche Zahl, die Sie durch wiederholtes Quadrieren verwenden könnenO(logn) Multiplikationen. Für anderen Multiplikation allein reicht nicht aus.
quelle
Die Leute haben dir gesagt, was wann passiertn 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:
quelle
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.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.
quelle