Java große integer?
Wenn man in java folgende rechenoperation hat:
5000^5000 mod 999
Dann wäre das ergebnis ja kleiner als 999 und somit als integer zu speichern
Aber kann java mit 5000^5000 überhaupt rechnen? (Die zahl hat 18000 stellen...)
Habs gerade ausprobiert jetzt kommt da 5005 raus was ja auch nicht sein kann
7 Antworten
Ein normaler Integer hat nur 32-bit und kann damit nur bis max. 2^31 - 1 rechnen (2.147.483.647).
In Java gäbe es auch noch Long, welcher bis zu 64-bit halten kann (2^63 - 1, also 9.223.372.036.854.775.807).
Für alles, was darüber geht, muss ein BigInt verwendet werden (bzw. BigDecimal bei Gleitkommazahlen).
In Java selbst wird es dabei zu einem integer overflow kommen, Integer sind durch 2e31 beschränkt. Es gibt jetzt im wesentlichen zwei Möglichkeiten, solche Berechnungen in Java anzustellen:
1. Verwende die Klasse java.math.BigIntegerBigInteger ist eine Klasse, die mit Zahlen jenseits der Wertebereiche der primitiven Datentypen rechnen kann (analog für Gleitkommazahlen gibt es im selben Paket noch die Klasse BigDecimal). Definiere dir also zwei Variablen und verwende die Methoden der Klasse, dann erhältst du das Ergebnis 601:
BigInteger b = new BigInteger("5000");
BigInteger m = new BigInteger("999");
BigInteger res = b.pow(5000).mod(m);
System.out.println(res.toString()); // 601
Natürlich kann man alles mit der Brechstange lösen, aber einfacher werden die meisten Berechnungen meistens, wenn man ein paar mathematische Überlegungen anstellt. Was du hier machen möchtest, ist diskret zu exponentieren. Dafür existiert ein auch bei sehr großen Zahlen noch relativ effizientes Verfahren, nämlich der Square-and-multiply-Algorithmus (binäre Exponentiation):
https://de.wikipedia.org/wiki/Bin%C3%A4re_Exponentiation
Eine sehr schöne Erklärung dazu findest du hier:
https://www.youtube.com/watch?v=5FJ7NJH_y74
Letztlich kein Hexenwerk, aber um Längen effizienter als naive Multiplikation, weil man durch iteriertes modulo-rechnen die Anzahl an Multiplikationen enorm reduziert und zusätzlich in "humanen" Zahlenbereichen bleibt. Eine Implementierung habe ich mal aus einem eigenen Projekt in Python rausgezogen, lässt sich aber auch einfach auf Java übertragen:
def exponentiateModular(a: int, b: int, n: int) -> int:
powersModN = [a] # a^k for each k <= b
while 2 ** len(powersModN) <= b:
powersModN.append(powersModN[-1] ** 2 % n)
res = 1
for i in range(log(b) // log(2) + 1):
if b & (1 << i):
res *= powersModN[i]
return res % n
LG
Man würde 5000^5000 nicht ausrechnen, wenn man das Ergebnis nur modulo 999 braucht.
Erstmal: Wie viele Stellen hätte 5000^5000? Das wären aufgerundet
log10 (5000^5000)
= 5000 * log10(5000)
= 5000 * log10(5 * 1000)
= 5000 * (3 + log10(5))
Jetzt ist log10(5) etwa 0.7, also hat die Zahl 5000 * 3.7 = 18500 Stellen.
Dann: Was ist 5000^5000 mod 999?
Also, erstmal kann man das mit ein wenig Übung recht elementar mit Hand ausrechnen; das Ergebnis ist 601.
Das das aber eine Programmieraufgabe ist, würde ich mir einen Algorithmus bauen:
1) Initialisier den integer x mit 1. Initialisiere n mit 5000
2) Multiplizieren x mit 5000, ziehe von n eins ab.
2) Ziehe von x so lange 999 ab, bis x < 999. Alternativ kannst du das mit einer Integer-Division und Multiplikation machen.
3) Wenn n > 0, dann bei 2) weiter. Wenn n = 0, dann steht in x das Ergebnis.
Dafür braucht man keine großen Zahlen, die maximale Zahl, die hier vorkommen kann, ist 998 * 5000.
In deinem Fall würde ich wahrscheinlich folgendes machen (ungetestet):
int result = new BigInteger("5000").pow(5000).mod(new BigInteger("999")).intValue();
Int:
-2147483648 bis 2147483647