java.math.BigInteger pow (Exponent) Frage

Question

Ich habe einige Tests auf Pow (Exponent) -Methode. Leider sind meine mathematischen Fähigkeiten nicht stark genug, um das folgende Problem zu lösen.

Ich verwende diesen Code:

BigInteger.valueOf(2).pow(var); 

Ergebnisse:

• var | Zeit in ms
• 2000000 |
• 2500000 |
• 3000000 | 22379
• 3500000 | 32147
• 4000000 |
• 4500000 |
• 5000000 | 49922

Sehen? 2.500.000 Exponenten werden fast so schnell wie 2.000.000 berechnet. 4.500.000 wird viel schneller als 4.000.000 berechnet.

Warum ist das?

Sie etwas Hilfe zu geben, ist hier die ursprüngliche Implementierung von BigInteger.pow (Exponent):

public BigInteger pow(int exponent) { 
    if (exponent < 0) 
     throw new ArithmeticException("Negative exponent"); 
    if (signum==0) 
     return (exponent==0 ? ONE : this); 

    // Perform exponentiation using repeated squaring trick 
     int newSign = (signum<0 && (exponent&1)==1 ? -1 : 1); 
    int[] baseToPow2 = this.mag; 
     int[] result = {1}; 

    while (exponent != 0) { 
     if ((exponent & 1)==1) { 
     result = multiplyToLen(result, result.length, 
             baseToPow2, baseToPow2.length, null); 
     result = trustedStripLeadingZeroInts(result); 
     } 
     if ((exponent >>>= 1) != 0) { 
       baseToPow2 = squareToLen(baseToPow2, baseToPow2.length, null); 
     baseToPow2 = trustedStripLeadingZeroInts(baseToPow2); 
     } 
    } 
    return new BigInteger(result, newSign); 
    } 

Answer 1

Der Algorithmus verwendet wiederholte Quadrierung (squareToLen) und Multiplikation (multiplyToLen).Die Zeit für diese Operationen hängt von der Größe der beteiligten Zahlen ab. Die Multiplikationen der großen Zahlen am Ende der Berechnung sind viel teurer als die am Anfang.

Die Multiplikation wird nur durchgeführt, wenn diese Bedingung zutrifft: ((exponent & 1)==1). Die Anzahl der quadratischen Operationen hängt von der Anzahl der Bits in der Anzahl ab (ohne führende Nullen), aber eine Multiplikation ist nur für die Bits erforderlich, die auf 1 gesetzt sind. Es ist einfacher, die Operationen zu sehen, die beim Betrachten der Binärdatei erforderlich sind Darstellung der Zahl:

 
2000000: 0000111101000010010000000 
2500000: 0001001100010010110100000 
3000000: 0001011011100011011000000 
3500000: 0001101010110011111100000 
4000000: 0001111010000100100000000 
4500000: 0010001001010101000100000 
5000000: 0010011000100101101000000 

Beachten sie, dass 2.5M und 4.5M Glück haben, dass sie sie umgebenden weniger hohe Bits als die Zahlen haben. Das nächste Mal, dies geschieht, ist bei 8.5M:

 
8000000: 0011110100001001000000000 
8500000: 0100000011011001100100000 
9000000: 0100010010101010001000000 

Die Sweet-Spots sind genau Potenzen von 2.

 
1048575: 0001111111111111111111111 // 16408 ms 
1048576: 0010000000000000000000000 // 6209 ms 

Answer 2

Nur eine Vermutung:

der Exponent gehandhabt wird Stück für Stück, und wenn das niedrigstwertige Bit ist 1 zusätzliche Arbeit ist erledigt.

Wenn L die Anzahl der Bits im Exponenten und A die Anzahl von Bits, die 1 und t1 die Zeit, den gemeinsamen Teil und t2 die zusätzliche Zeitverarbeitung zu verarbeiten, wenn die LSBit 1

dann würde die Laufzeit

L t1 + A

oder die Zeit, von der Anzahl von 1-en in der Binärdarstellung abhängig t2 sein.

jetzt ein kleines Programm zu schreiben, meine Theorie zu überprüfen ...

Answer 3

Ich bin nicht sicher, wie oft Sie Ihre Timings ausgeführt haben. Wie einige der Kommentatoren darauf hingewiesen haben, müssen Sie die Operationen viele Male wiederholen, um gute Ergebnisse zu erzielen (und sie können immer noch falsch liegen).

Angenommen, Sie haben die Zeit gut geplant, denken Sie daran, dass es viele Verknüpfungen gibt, die in Mathe verwendet werden können. Sie müssen die Operationen 5 * 5 * 5 * 5 * 5 * 5 nicht ausführen, um 5^6 zu berechnen.

Hier ist eine Möglichkeit, es viel schneller zu tun. http://en.wikipedia.org/wiki/Exponentiation_by_squaring