Fixing rekursive Exponentiation Methode?

Question

Ich arbeite gerade an einer Methode, um eine Exponentiationsrechnung mit Rekursion durchzuführen. Hier ist, was ich bis jetzt habe:

public static long exponentiation(long x, int n) { 

    if (n == 0) { 
     return 1; 
    } else if (n == 1) { 
     return x; 
     // i know this doesn't work since im returning long 
    } else if (n < 0) { 
     return (1/exponentiation(x, -n)); 
    } else { 
     //do if exponent is even 
     if (n % 2 == 0) { 
      return (exponentiation(x * x, n/2)); 
     } else { 
      // do if exponent is odd 
      return x * exponentiation(x, n - 1); 
     } 
    } 
} 

Ich habe zwei Probleme. Das erste Problem ist, dass ich keine negativen Exponenten machen kann, dies ist kein großes Problem, da ich keine negativen Exponenten machen muss. Zweite Frage, bestimmte Berechnungen geben mir die falsche Antwort. Zum Beispiel gibt 2^63 mir den richtigen Wert, aber es gibt mir eine negative Zahl. Und 2^64 und gib mir einfach 0. Gibt es trotzdem etwas für mich, das zu beheben? Ich weiß, dass ich einfach die long 's zu double wechseln könnte und meine Methode wird perfekt funktionieren. Mein Professor hat uns jedoch gebeten, long zu verwenden. Danke für Ihre Hilfe!

Answer 1

Der maximale Wert, den ein long darstellen kann, ist 2^63 -1. Wenn Sie also 2^63 berechnen, ist es größer als das, was ein Langer halten und umschlingen kann. Long wird mit twos-complement dargestellt.

Nur lang zu verdoppeln funktioniert nicht genau. Es ändert die Semantik der Methode. Fließkommazahlen haben eine begrenzte Genauigkeit. Mit einer 64-Bit-Fließkommazahl können Sie immer nur die gleiche Anzahl von Zahlen wie bei einer 64-Bit-Ganzzahl darstellen. Sie sind nur unterschiedlich verteilt. ein langer kann jede ganze Zahl zwischen -2^63 und 2^63-1 darstellen. Ein Double kann auch Brüche von Zahlen darstellen, aber bei hohen Zahlen kann es nicht jede Zahl darstellen.

Zum Beispiel verdoppelt die nächste Sie repräsentieren nach 100000000000000000000000000000000000000000000000000 100000000000000030000000000000000000000000000000000 ist - so sind Sie missiong eine satte 30000000000000000000000000000000000 Sie nicht mit einem Doppel darstellen kann.

Sie versuchen, etwas zu reparieren, das Sie nicht reparieren sollten. Bei Verwendung von long gibt es einen festen maximalen Rückgabewert, den Ihre Methode möglicherweise zurückgibt. Ihre Methode sollte klar angeben, was passiert, wenn sie überläuft, und Sie möchten möglicherweise solche Überläufe behandeln (z. B. mit Math#multiplyExactly), aber wenn long ist der Rückgabewert, den Sie zurückgeben sollen, dann sollten Sie das verwenden.

Answer 2

Sie könnten das Ergebnis in einem Array von Longs halten, nennen wir es result[]. Wenden Sie zuerst die Logik auf result[0] an. Aber wenn dieser Wert negativ wird,

1) inkrement result[1] durch den Überschuss. 2) jetzt wird Ihre Logik viel unordentlicher und ich tippe auf meinem Handy, so dass dieser Teil als Übung für den Leser übrig ist. 3) Wenn result[1] überläuft, starten Sie am result[2]...

Wenn Sie das Ergebnis drucken, kombinieren Sie die Ergebnisse wiederum Logik unordentlich.

Ich nehme an, so funktioniert BigInteger (mehr oder weniger)? Ich habe mir diesen Code nie angesehen, vielleicht möchten Sie das.

Aber im Grunde ist Polygnone korrekt. Ohne erhebliche Umgehungslösungen gibt es eine obere Grenze.