Wie kann ich Potenzen mit besserer Laufzeit berechnen?
z. 2 ^ 13.
Ich erinnere mich, irgendwo gesehen zu haben, dass es etwas mit der folgenden Berechnung zu tun hat:
2 ^ 13 = 2 ^ 8 * 2 ^ 4 * 2 ^ 1
Aber ich kann nicht sehen, wie es mir helfen würde, jede Komponente der rechten Seite der Gleichung zu berechnen und sie dann zu multiplizieren.
Irgendwelche Ideen?
Edit: Ich meinte mit jeder Basis. Wie verbessern die unten erwähnten Algorithmen, insbesondere die "Exponentierung durch Quadrieren", die Laufzeit / Komplexität?
Es gibt einen verallgemeinerten Algorithmus dafür, aber in Sprachen, die Bit-Shifting haben, gibt es eine viel schnellere Möglichkeit, Potenzen von 2 zu berechnen. Sie geben einfach 1 << exp ein (vorausgesetzt, Ihr Bit-Shift-Operator ist << wie er ist) ist in den meisten Sprachen, die die Operation unterstützen).
Ich nehme an, Sie suchen nach dem verallgemeinerten Algorithmus und wählen einfach eine unglückliche Basis als Beispiel. Ich werde diesen Algorithmus in Python geben.
%Vor%Dies bewirkt, dass Exponenten in log2 exp time berechnet werden können. Es ist ein Divide and Conquer-Algorithmus. :-) Wie jemand anderes Potenzierung durch Quadrierung sagte.
Wenn Sie Ihr Beispiel damit verbinden, können Sie sehen, wie es funktioniert und mit der von Ihnen gegebenen Gleichung in Beziehung steht:
%Vor%Sie können die Potenzierung durch Quadrieren verwenden. Dies wird auch als "Quadrat-und-Multiplizieren" bezeichnet und funktioniert auch für Basen! = 2.
Wenn Sie sich nicht auf Zweierpotenzen beschränken, dann:
k ^ 2n = (k ^ n) ^ 2
Der schnellste freie Algorithmus, den ich kenne, stammt von Phillip S. Pang, Ph.D und kann den Quellcode enthalten hier gefunden.
Es verwendet eine tabellengesteuerte Zerlegung, mit der es möglich ist, die Funktion exp (), die 2-10 mal schneller ist, als native exp () des Pentium (R) -Prozessors zu machen.