Montag, 2. Juni 2014

Große Zahlen verwalten mit der Klasse BigInteger

Wie eigentlich in jeder Programmiersprache auch sind in C# die Standarddatentypen begrenzt, sie können keine Zahlen beliebiger Größe aufnehmen. Heute möchte ich zeigen, wie man doch mit Zahlen quasi beliebiger Größe rechnen kann. Dafür benutzen wir den Datentyp BigInteger, welcher ganze Zahlen darstellen kann. Dieser befindet sich im Namespace System.Numerics, welchen wir erst einbinden müssen: Dazu klicken wir auf Projekt - Verweis hinzufügen und wählen dann unter Assemblys System.Numeric aus.
Nun steht uns der gewünschte Datentyp zu Verfügung, welcher eine Struktur ist und verschiedene nützliche Methoden bereitstellt.
Folgender Code z.B. erstellt 2 BigInteger Zahlen und addiert diese:
System.Numerics.BigInteger A = new System.Numerics.BigInteger(100);
System.Numerics.BigInteger B = new System.Numerics.BigInteger(200);
System.Numerics.BigInteger Result = System.Numerics.BigInteger.Add(A, B);

Wie man sieht, stellt BigInteger eine statische Funktion zum Addieren zweier Zahlen bereit. Natürlich gibt es auch Funktionen für das Multiplizieren etc. Allerdings können in C# Operatoren überladen werden, was hier auch gemacht wurde, und so kann man glücklicherweise mit BigInteger Zahlen fast genauso wie mit herkömmlichen Datentypen umgehen. Der nachfolgende Code ist analog zum obigen:
System.Numerics.BigInteger A = 100;
System.Numerics.BigInteger B = 200;
System.Numerics.BigInteger Result = A + B;

Beim Potenzieren allerdings gibt es keine Überladung der Funktion, da wir ja hierfür die statische Funktion Math.Pow() verwenden würden, welche 2 double Werte erwartet. Deshalb benutzen wir zum Potenzieren die Funktion BigInteger.Pow().
Abschließend noch ein paar Anmerkungen zur Division: Da, wie bereits erwähnt, BigInteger nur ganze Zahlen darstellen kann, kann man hiermit keine genaue Division durchführen. Einerseits könnte man die Klasse BigRational verwenden, welche ich im nächsten Post vorstellen werde.
Oft kann man aber den Code auch so umschreiben, dass die Zahlen zuerst kleiner werden und man dann einen double oder ähnliches zur Division nutzen kann.
Oder, man benutzt folgenden interessanten Trick:
double Result = Math.Exp(System.Numerics.BigInteger.Log(A) - System.Numerics.BigInteger.Log(B));

Auf Grund der Potenzgesetze entspricht nämlich A / B = Exp(Log(a / b)) = Exp(Log(a) - Log(b)). Der Logarithmus verkleinert die Zahlen A und B erheblich, das Ergebnis ist ein double - wenn das also vom Wertebereich her passt, kann so eine Gleitkommadivisision ausgeführt werden. Natürlich gehen so aber, je nach Zahl, einige Stellen an Genauigkeit verloren.

Keine Kommentare:

Kommentar veröffentlichen