Was ist der schnellste Algorithmus für die Exponentiation? Lassen Sie uns der Einfachheit halber natürliche Zahlenbasen und Exponenten annehmen.
Was würde eine effiziente Mathematikbibliothek verwenden?
(Wenn ich danach suche, erhalte ich nur Ergebnisse, die sich auf Algorithmen beziehen, die in exponentieller Zeit laufen.)
Das Problem mit allen obigen binären Methoden ist, dass sie nur auf ganze Zahlen beschränkt sind. Wenn Sie unter "Exponentiation" die Funktion e ^ x berechnen, ist das Beste, was ich gesehen habe, Potenzreihen, die schnell konvergieren, und polynomiale, rationale oder Pade-Approximationen, die über einen begrenzten Bereich gültig sind.
Eines ist sicher: Wenn Sie einen blitzschnellen Algorithmus für e ^ x auf 96 Dezimalstellen finden, haben Sie auch einen schnelleren Weg gefunden, Logs zu berechnen (von Newton-Raphson). Tatsächlich konvergiert Newton-Raphson quadratisch, so dass Sie die Anzahl der Stellen in Ihrem Protokoll mit jeder Iteration verdoppeln. Dies war ein Favorit von Nate Grossman von UCLA in den frühen Tagen.
In den Tagen der Vier-Taschenrechner habe ich e ^ x = (1 + x / 1024) ^ 10 benutzt. Natürlich bricht das für x sehr groß oder sehr klein zusammen, aber Sie können sehen, warum es funktioniert. Wenn Sie eine Quadratwurzel-Schaltfläche haben, können Sie diese Idee umkehren, um Logarithmen zu erhalten. Aber Sie brauchen keine Quadratwurzel für die Exponentialfunktion.
Ich frage mich, ob es eine Inversion des AGM-Algorithmus gibt, der die Exponentialfunktion ausführen könnte ... Hmmm ....
Für kleine Exponenten verwendet Python die binäre Potenzierung (eine Potenzierung durch Quadrieren), wie in Zeile 2874 von Ссылка
Für größere Exponenten verwendet es eine 2 ^ 5-artige Potenzierung (eine alternative Art der Potenzierung durch Quadrieren).
Wenn Sie nur die höchstwertigen Ziffern des Ergebnisses interessieren, können Sie sehr schnell x ^ y = exp (y * log (x)) berechnen.
Wenn Sie nur die niedrigstwertigen Stellen des Ergebnisses interessieren (zB für einen Programmierwettbewerb), dann können Sie den Exponenten modulo einen Wert M berechnen. Zum Beispiel wird der Python-Befehl pow (x, y, 1000) berechnet die letzten 3 Ziffern von x zur Potenz von y. Dies geschieht durch die Potenzierung durch Quadrierungsmethode, aber beachten Sie, dass dies viel schneller sein kann als die Berechnung des vollständigen Ergebnisses, da es sicherstellt, dass die Zwischenzahlen niemals größer als M sind.
Als zusätzlichen Twist (wenn Sie nur an den kleinsten Zeichen interessiert sind), können Sie das Eulersche Theorem Ссылка um die Größe des Exponenten zu reduzieren.
Wenn Sie eine gegebene natürliche Zahl u und eine gegebene Eingabe m haben, können Sie zur Berechnung von u ^ m den folgenden Algorithmus anwenden
%Vor%Also im Grunde, wenn du, sagen wir, hast du 23 Sie konvertieren 23 in Binär - & gt; 10111 (Basis 2) Dann bekommst du ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Die Komplexität ist O (log (m)) oder O (n), wenn Sie n als log (m) _10 + 1
betrachtenTags und Links algorithm language-agnostic math