Rechenleistungen (zum Beispiel 2^11) schnell

Question

Mögliche Duplizieren:
The most efficient way to implement an integer based power function pow(int, int)

Wie kann ich berechnen Kräfte mit besserer Laufzeit?

z. 2^13.

Ich erinnere mich, irgendwo, dass es etwas mit der folgenden Berechnung zu tun hat:

2^13 = 2^8 * 2^4 * 2^1

Aber ich kann nicht sehen, wie die Berechnung jede Komponente der rechten Seite der Gleichung und dann multiplizieren sie würde mir helfen.

Irgendwelche Ideen?

Edit: Ich meinte mit jeder Basis. Wie verbessern die unten erwähnten Algorithmen, insbesondere die "Exponentierung durch Quadrieren", die Laufzeit/Komplexität?

Answer 1

Es ist eine verallgemeinerte Algorithmus für diese, aber in Sprachen, die Bit-Verschiebung haben, gibt es eine viel schnellere Art und Weise Potenzen von 2 zu berechnen Sie nur in 1 << exp setzen (Ihre Bit-Shift-Operator unter der Annahme <<, wie es in den meisten ist Sprachen, die den Vorgang unterstützen).

Ich nehme an, Sie suchen nach dem verallgemeinerten Algorithmus und wählen nur eine unglückliche Basis als Beispiel. Ich werde diesen Algorithmus in Python geben.

def intpow(base, exp): 
    if exp == 0: 
     return 1 
    elif exp == 1: 
     return base 
    elif (exp & 1) != 0: 
     return base * intpow(base * base, exp // 2) 
    else: 
     return intpow(base * base, exp // 2) 

Dies bewirkt grundsätzlich, dass Exponenten in log2 exp Zeit berechnet werden können. Es ist ein Divide and Conquer-Algorithmus. :-) Wie jemand anderes sagte exponentiation by squaring.

Wenn Sie Ihr Beispiel in diesem Stecker können Sie sehen, wie es funktioniert und ist auf die Gleichung Sie geben:

intpow(2, 13) 
2 * intpow(4, 6) 
2 * intpow(16, 3) 
2 * 16 * intpow(256, 1) 
2 * 16 * 256 == 2^1 * 2^4 * 2^8 

Answer 2

Zweierpotenzen sind die leichte. In binär 2^13 ist eine Eins gefolgt von 13 Nullen.

Sie würden Bit Shifting verwenden, das ein eingebauter Operator in vielen Sprachen ist.

Answer 3

Sie können exponentiation by squaring verwenden. Dies wird auch als "Quadrat-und-Multiplizieren" bezeichnet und funktioniert auch für Basen! = 2.

Answer 4

Wenn Sie zu begrenzen sich nicht auf Potenzen von zwei, dann gilt:

k^2n = (k^n)^2

Answer 5

Verwendung bitweise Verschiebung. Ex. 1 < < 11 gibt 2^11 zurück.

Answer 6

Der schnellste freie Algorithmus, den ich kenne, ist durch Phillip S. Pang, Ph.D und der Quellcode kann here gefunden werden. Es verwendet tabellengesteuerte Dekomposition, mit der es möglich ist, exp() -Funktion zu machen, die 2-10 mal schneller ist, als native exp() des Pentium (R) -Prozessors.