Wie heben Sie einen Java BigInteger auf die Leistungsfähigkeit eines BigIntegers auf, ohne modulare Arithmetik zu verwenden?

Question

Ich mache ein großes Integer-Computing, und ich muss einen BigInteger auf die Macht eines anderen BigInteger bringen. Die .pow() -Methode tut was ich will, nimmt aber einen int-Wert als Argument. Die .modPow-Methode verwendet einen BigInteger als Argument, aber ich möchte keine Antwort, die mit dem Wert übereinstimmt, den ich zu berechnen versuche.

Mein BigInteger-Exponent ist zu groß, um als int dargestellt zu werden. Kann jemand einen Weg vorschlagen, um diese Einschränkung zu umgehen?

Answer 1

Sie sollten nicht versuchen, die Macht einer extrem großen Zahl mit einer anderen extrem großen Zahl zu berechnen. Die resultierende Zahl würde große Mengen an Speicher verbrauchen. Wenn Sie a.pow(b) berechnen, wird es ungefähr log(a)*b Ziffern haben. Wenn b zu groß ist, um in eine ganze Zahl zu passen, dann wird das Ergebnis selbst für ziemlich kleine Werte von a mehrere Milliarden Ziffern haben.

Versuchen Sie zu überdenken, was Sie erreichen möchten und wie Sie es erreichen können, ohne diesen Vorgang auszuführen.

Answer 2

Die praktische Lösung besteht darin, den Exponenten von einem BigInteger in einen int zu konvertieren.

Wenn Sie dies nicht tun können, weil der Exponent zu groß ist, ist Ihr Algorithmus nicht implementierbar. Die resultierende Zahl wäre fast sicher zu groß, um sie als BigInteger darzustellen. (Ein BigInteger verwendet ein Array von Bytes zur Darstellung der Zahl, und die maximale Größe eines Java-Arrays ist 2**31 - 1 Elemente, egal wie groß der Heap ist.) Und selbst wenn Sie eine "BiggerInteger" -Klasse implementiert haben, die die Zahl darstellen würde würde bald die Grenzen der physischen Speichergröße Ihrer Maschine überschreiten. (Und die Zeit zu berechnen N.pow(M) wäre ... NP-tricky ... O((MlogN)^M) Ich denke).

Natürlich, wenn die Zahl, die Sie die Macht nehmen von 0 ist, 1 oder -1, dann wird das Ergebnis leicht in einem BigInteger passen. Aber in diesen Fällen gibt es bessere Möglichkeiten, die Leistung zu berechnen :-).