Exakte Arithmetik ganzer Zahlen

1. Aufgabe

Die ganzzahligen Standarddatentypen in .NET wie short, int usw. besitzen allesamt die Eigenschaft, dass ihr Wertebereich limitiert ist. Für viele Anwendungen ist dies nicht nachteilig, da sich speziell mit den Datentypen int und long ziemlich große Zahlen darstellen lassen. Für manche Anwendungen ist die Verarbeitung von ganzen Zahlen beliebiger Größe jedoch unabdingbar. Wir stellen im Folgenden eine Klasse BigInteger vor, die eine exakte Arithmetik vorzeichenbehafteter ganzer Zahlen beliebiger Größe zur Verfügung stellt.

Um potentiell beliebig viele Ziffern einer sehr großen Zahl in einem BigInteger-Objekt abzulegen, gibt es mehrere Möglichkeiten wie etwa die Verwendung (generischer) Standardcontainer (zum Beispiel die Klassen ArrayList oder List<int>) oder auch Zeichenketten (Klasse String). Noch grundlegender geht es unter Zuhilfenahme eines Arrays, dessen Elemente die einzelnen Ziffern der sehr großen Zahl aufnehmen. In der vorgestellten Lösung zu dieser Aufgabe verwenden wir diesen Ansatz.

Unsere Kenntnisse aus der Schulmathematik zur schriftlichen Addition, Multiplikation usw. sind die Basis für die Implementierung der arithmetischen Operatoren. Vermutlich liegen Ihre Erinnerungen hierzu, so wie meine auch, zwischenzeitlich in einem recht verschwommen Zustand vor. Zu diesem Zweck finden Sie in den nachfolgenden Hinweisen einen kleinen Auffrischungskurs der entsprechenden schulmathematischen Grundlagen vor.

Um etwaige Missverständnisse rechtzeitig auszuräumen: In der Implementierung Ihrer Klasse BigInteger dürfen Sie zum Rechnen mit einzelnen Ziffern – aus denen die sehr großen Zahlen gebildet werden – selbstverständlich die Standardoperatoren von C# wie + oder * verwenden. Ziel dieser Fallstudie ist es, einen Klassentyp zu entwickeln, der die Wertebereichslimitierungen dieser elementaren ganzzahligen Datentypen überwindet.

Das Grundgerüst der BigInteger-Klasse finden Sie in Tabelle 1 beschrieben vor:

Element

Beschreibung

Konstruktor

public BigInteger ();

Erzeugt ein BigInteger-Objekt für die Zahl 0.

Konstruktor

public BigInteger (String number);

Erzeugt ein BigInteger-Objekt mit Hilfe der Beschreibung einer Zahl in Form einer Zeichenkette. Die Zeichenkette darf optional mit einem Plus- oder Minuszeichen beginnen, um das Vorzeichen der Zahl festzulegen. Danach folgen beliebig viele dezimale Ziffern:

BigInteger a = new BigInteger("+12345678901234567890");

Der besseren Lesbarkeit halber sind Punkte in der Zeichenkette zulässig, wie etwa

BigInteger a = new BigInteger("+12.345.678.901.234.567.890");

Konstruktor

public BigInteger (int n);
public BigInteger(long n);

Erzeugt ein BigInteger-Objekt zu einem int- bzw. long-Wert.

Eigenschaft Sign

public bool Sign { get; }

Liefert das Vorzeichen der Zahl zurück, true entspricht einer positiven Zahl, false einer negativen.

Eigenschaft Cardinality

public int Cardinality { get; }

Liefert die Anzahl der Ziffern der Zahl, auch Stelligkeit der ganzen Zahl genannt, zurück.

Eigenschaft IsZero

public bool IsZero { get; }

Liefert true zurück, wenn die Zahl den Wert 0 besitzt, andernfalls false.

Konvertierungsoperatoren (implizit)

public static implicit operator BigInteger (int n);
public static implicit operator BigInteger (long n);
public static implicit operator BigInteger (String s);

Konvertierungsoperatoren zur Umwandlung eines int- bzw. long-Werts in ein BigInteger-Objekt.

Konvertierungsoperatoren (explizit)

public static explicit operator int  (BigInteger a);
public static explicit operator long (BigInteger a);

Konvertierungsoperatoren zur Umwandlung eines BigInteger-Objekts in einen int- bzw. long-Wert. Da bei zu großen Werten in einem BigInteger-Objekt die Umwandlung nicht möglich ist (Informationsverlust), muss die Umwandlung explizit durch einen entsprechenden Cast-Operator angezeigt werden.

Operatoren == bzw. !=

public static bool operator== (BigInteger a, BigInteger b);
public static bool operator!= (BigInteger a, BigInteger b);

Vergleicht den Wert zweier BigInteger-Objekte auf Gleichheit bzw. Ungleichheit.

Operatoren <, <=, > bzw. >=

public static bool operator<  (BigInteger a, BigInteger b);
public static bool operator<= (BigInteger a, BigInteger b);
public static bool operator>  (BigInteger a, BigInteger b);
public static bool operator>= (BigInteger a, BigInteger b);

Umsetzung der mathematischen Relationen kleiner, kleiner-gleich, größer und größer-gleich auf zwei BigInteger-Objeke mittels der binären Operatoren <, <=, > und >=.

Methode Abs

public BigInteger Abs();

Liefert ein BigInteger-Objekt mit dem Absolutbetrag des aktuellen Objekts zurück.

Methode ToString

public override String ToString ();

Konvertiert den numerischen Wert des Objekts in eine äquivalente Zeichenkettendarstellung. Um die Lesbarkeit der Zeichenfolge zu steigern, ist nach jeder dritten Stelle ein Punkt einzufügen, also zum Beispiel "99.999". Die Anzahl der Dreiziffernblöcke, die in einer Zeile stehen sollen, kann mit einem Formatspezifizierer festgelegt werden:

BigInteger n = new BigInteger("123.456.789.012.345.678.901.234");
Console.WriteLine("{0:4}", n.ToString());

Ausgabe der Zeichenkette in einer Konsole:

123.456.789.012.
345.678.901.234

In die Zeichenkette ist an den entsprechenden Stellen ein Zeilenumbruch einzufügen (Environment.NewLine).

Tabelle 1. Elemente der Klasse BigInteger.


Wir geben nun einige Hinweise zu den Grundrechenarten, wie sie in der Schulmathematik gelehrt werden. Bei der so genannten schriftlichen Addition werden die zu addierenden Zahlen rechtsbündig so angeordnet, dass jeweils gleichwertige Ziffern (Einer unter Einer, Zehner unter Zehner usw.) untereinander stehen. Man addiert dann jeweils untereinander stehende Ziffern, beginnend mit den Einern. Ein Beispiel dazu finden Sie in Abbildung 1 vor:

Schriftliche Addition der Schulmathematik – ohne Überlauf.

Abbildung 1. Schriftliche Addition der Schulmathematik – ohne Überlauf.


Ein kleines Problem bleibt da aber noch: Angenommen, in einer Spalte kommt eine Summe von 10 oder mehr heraus? In dieser Situation findet ein Übertrag statt, d.h. wenn zum Beispiel in einer Spalte die Zahl 13 rechnerisch heraus kommen würde, notiert man in dieser Spalte nur 3 als Additionsergebnis (also 10 weniger), in der nächsten Spalte weiter links wird dafür zusätzlich eine 1 mit addiert, um in dieser Spalte die fehlende 10 aus der Spalte vorher auszugleichen. Auch für diese Situation sollten wir ein Beispiel betrachten, die – etwas kleiner – gesetzten 1-er unterhalb der beiden Summanden in Abbildung 2 stellen jeweils einen Überlauf dar:

Schriftliche Addition der Schulmathematik – mit Überlauf.

Abbildung 2. Schriftliche Addition der Schulmathematik – mit Überlauf.


Bei der Umsetzung der schriftlichen Addition in ein Programm stellt sich die Frage, in welcher Reihenfolge die einzelnen Ziffern im korrespondierenden Array des BigInteger-Objekts abgelegt werden. Da die einzelnen Ziffern stellenweise, beginnend mit der niedrigstwertigen Stelle, zu addieren sind, bietet es sich an, die einzelnen Ziffern in umgekehrter Reihenfolge im Array abzuspeichern. Wenn wir das Beispiel aus Abbildung 2 noch einmal betrachten, so würde bei dieser Vorgehensweise die Ablage und Verarbeitung der beiden Zahlen 28345 und 7567 in einem BigInteger-Objekt wie in Abbildung 3 aussehen:

Ablage der Ziffern in umgekehrter Reihenfolge in einem BigInteger-Objekt.

Abbildung 3. Ablage der Ziffern in umgekehrter Reihenfolge in einem BigInteger-Objekt.


Die schriftliche Subtraktion funktioniert prinzipiell zunächst einmal so wie die schriftliche Addition. Beginnend mit der niedrigstwertigen Stelle wird Stelle für Stelle die Ziffer des Subtrahenden (untere Ziffer) von der Ziffer des Minuenden (obere Ziffer) abgezogen. Ein Problem entsteht, wenn die obere Ziffer kleiner ist als die dazugehörige untere des Subtrahenden, so dass die Subtraktion der zwei Ziffern nicht durchgeführt werden kann. Hier gibt es mehrere Verfahren zur Lösung des Problems. Wir skizzieren im Folgenden das so genannte Entbündelungsverfahren. Subtrahieren mit Entbündeln bedeutet, dass der zu kleine Minuend bei seinem linken Nachbarn eine Anleihe macht. Durch Borgen von der nächsthöheren Stelle wird die Ziffer des Minuenden um 10 erhöht, und zum Zwecke des Ausgleichs die nächsthöherwertige Ziffer des Minuenden um 1 erniedrigt. Auf diese Weise kann man stets erreichen, dass die untenliegende Ziffer von der obenliegenden Ziffer abgezogen werden kann, wie wir im Beispiel aus Abbildung 4 vorführen:

Entbündelungsverfahren für Subtraktion.

Abbildung 4. Entbündelungsverfahren für Subtraktion.


Die Subtraktion der Einerstellen in Abbildung 4 bereitet keine Probleme, 4 minus 2 ist gleich 2. Die Zehnerstellen lassen sich nicht abziehen, der Minuend (6) ist zu klein. Er wird darum um 10 erhöht, also gleich 16 gesetzt. Diese 10 wird von der links daneben stehenden Ziffer (8) geliehen und deshalb wird diese um 1 erniedrigt (neuer Wert 7). Nun können die nächsten zwei Subtraktionen (16 minus 9 und 7 minus 5) problemlos durchgeführt werden und man erhält 272 als korrektes Gesamtergebnis der Subtraktion.

Hinweis: Einen Sonderfall müssen Sie in Ihrer Implementierung noch beachten, nämlich wenn beim Leihen die korrespondierende Ziffer des Minuenden gleich 0 ist. Von 0 lässt sich bekanntermaßen nichts borgen (ein Wert -1 stellt hier keine Lösung des Problems dar), es muss folglich Stelle für Stelle in Richtung der höherwertigen Stellen solange weitergesucht werden, bis eine erste Ziffer ungleich 0 vorliegt. Nun kann hier der Leihvorgang stattfinden und der geliehene Wert über alle Zwischenstellen nach unten durchgereicht werden. In Abbildung 5 finden Sie ein Beispiel für diese Situation vor. Um 1 von 1000 abzuziehen, muss zum Leihen drei Stellen nach links gegangen werden:

Entbündelungsverfahren mit Null als linkem Nachbarn.

Abbildung 5. Entbündelungsverfahren mit Null als linkem Nachbarn.


Damit sind wir bei der Multiplikation angekommen. Das Standardverfahren beruht darin, die erste Zahl mit den einzelnen Ziffern der zweiten Zahl nacheinander zu multiplizieren, beginnend bei der letzten Stelle. Für jede neue Ziffer wird eine neue Zeile benötigt. Man schreibt jede Multiplikation untereinander und addiert die einzelnen Werte. Wie bei der Addition ist auch bei der Multiplikation ein Überlauf auf die jeweils nächsthöhere Stelle zu übertragen.

Im Gegensatz zum Standardverfahren der Schulmathematik vereinfachen wir das Verfahren dahingehend, dass wir in den einzelnen Zeilen zunächst keinen Überlauf berücksichtigen. Dies tun wir erst, wenn wir die Zwischenresultate der einzelnen Zeilen Spalte für Spalte, von rechts beginnend, zusammenzählen. Am Beispiel von 98 * 12345 können Sie den Algorithmus in Abbildung 6 nachverfolgen:

Standardverfahren der schriftlichen Multiplikation.

Abbildung 6. Standardverfahren der schriftlichen Multiplikation.


Damit sind wir bei der schriftlichen Division angekommen. Bezüglich der Namensgebung rekapitulieren wir zunächst einmal, dass ein Dividend durch einen Divisor geteilt wird, das Ergebnis heißt Quotient, der in unserem Fall stets ganzzahlig ist und aus diesem Grund in den meisten Fällen noch um einen Rest zu ergänzen ist. Wir beginnen mit der ersten (führenden) Zahl des Dividenden. Ist diese Zahl nicht größer als der Divisor, nehmen wir die nächste Zahl des Dividenden mit hinzu und wiederholen diesen Vorgang solange, bis die auf diese Weise gebildete Zahl größer ist als der Dividend. Nun teilen wir diese Zahl durch den Divisor, das Ergebnis bildet die erste Ziffer des gesuchten Quotienten. Um die Division fortsetzen zu können, multiplizieren wir das Ergebnis mit dem Divisor, und subtrahieren das Produkt von der alten Zahl. Das so erhaltene Ergebnis wird durch Herunterziehen der nächsten Ziffer von oben ergänzt. Dieses Procedere beginnen wir nun wieder von vorne. Der neue Dividend ist das Ergebnis der letzten Subtraktion, ergänzt um die heruntergezogene Ziffer usw.

Das ganze Verfahren wird solange wiederholt, bis alle Stellen des Dividenden nach unten gezogen wurden. Die unterste Zahl stellt den Rest der Division dar, der gesuchte Quotient wurde Ziffer für Ziffer zusammengesetzt. Möglicherweise ist diese textuelle Beschreibung des Divisionsalgorithmus etwas schwer verdaulich, zur Illustration betrachten wir in Abbildung 7 das folgende Beispiel:

Standardverfahren der schriftlichen Division.

Abbildung 7. Standardverfahren der schriftlichen Division.


Nach diesen Hilfestellungen fassen wir die soeben besprochenen arithmetischen Operatoren und Methoden für eine Ergänzung der BigInteger-Klasse in Tabelle 2 zusammen:

Element

Beschreibung

Operator +

public static BigInteger operator+ (BigInteger a, BigInteger b);

Liefert ein neues BigInteger-Objekt mit dem Wert a+b zurück.

Operator -

public static BigInteger operator- (BigInteger a, BigInteger b);

Liefert ein neues BigInteger-Objekt mit dem Wert a-b zurück.

Operator *

public static BigInteger operator* (BigInteger a, BigInteger b);

Liefert ein neues BigInteger-Objekt mit dem Wert a*b zurück.

Operator /

public static BigInteger operator/ (BigInteger a, BigInteger b);

Liefert ein neues BigInteger-Objekt mit dem Wert a/b zurück (ganzzahlige Division).

Operator %

public static BigInteger operator% (BigInteger a, BigInteger b);

Liefert ein neues BigInteger-Objekt mit dem Wert a%b zurück (Rest bei ganzzahliger Division).

Operatoren ++ bzw. --

public static BigInteger operator++ (BigInteger a);
public static BigInteger operator-- (BigInteger a);

Liefert ein neues BigInteger-Objekt mit dem Wert a+1 (Inkrement) bzw. a-1 (Dekrement) zurück. Beachten Sie: Die Unterscheidung zwischen Postfix- und Präfix-Inkrement (bzw. Dekrement) spiegelt sich in der Implementierung nicht wieder. Der Compiler erzeugt durch geeignete Verwendung temporärer Variablen das Postfix- und Präfix-Verhalten selbst.

Methode Power

public BigInteger Power (int exponent);

Liefert ein neues BigInteger-Objekt mit dem Wert thisexponent zurück. Der Wert des Exponenten ist dabei vom Typ int. Beachten Sie: Es sind nur Exponenten größer-gleich Null zulässig, da andernfalls das Resultat nicht mehr ganzzahlig wäre.

Tabelle 2. Arithmetische Operatoren und Methoden der Klasse BigInteger.


Zusätzlich zu den Elementen aus Tabelle 2 sind die Methoden der .NET-Standardschnittstellen IComparable und ICloneable zu implementieren.

2. Lösung

Die Realisierung der Klasse BigInteger ist nicht in allen Teilen trivial. Wir gehen die einzelnen Abschnitte detailliert durch. Die notwendigen Instanzvariablen einer Klasse BigInteger wurden durch die Aufgabenstellung mehr oder minder nahe gelegt:

private int[] digits;
private bool sign;

Die einzelnen Ziffern der großen Zahl sind in einem Array digits des Typs int abzulegen. Für das Vorzeichen der Zahl benötigen wir eine zusätzliche Instanzvariable sign, der Datentyp bool gestattet es, positive Zahlen mit dem Wert true und negative Zahlen mit false zu assoziieren. Der Standardkonstruktor soll die Zahl 0 repräsentieren, dazu benötigen wir immerhin ein Ziffernfeld der Länge 1:

// default c'tor
public BigInteger()
{
    this.digits = new int[1];
    this.digits[0] = 0;
    this.sign = true;
}

Der wichtigste Konstruktor der BigInteger erwartet eine (beliebig lange) Zeichenkette und kopiert ihren Inhalt, abgesehen von den Punkten . für die verbesserte Lesbarkeit, in das digits-Array um. Da man die Anzahl der Ziffern in der Zeichenkette nicht von vorne herein kennt, hat man keine andere Wahl, als diese zwei Mal zu traversieren: Einmal zum Zählen der Ziffern und ein zweites Mal zum Umkopieren (Listing 1). Prinzipiell wird von der Zeichenkette erwartet, dass diese korrekt aufgebaut ist, eine Fehlerüberprüfung würde den Quellcode eher unübersichtlich machen.

01: public BigInteger(String s)
02: {
03:     // count number of digits
04:     int count = 0;
05:     for (int i = 0; i < s.Length; i++)
06:         if (Char.IsDigit(s[i]))
07:             count++;
08: 
09:     // set sign
10:     this.sign = (s[0] == '-') ? false : true;
11: 
12:     // copy digits into array in reverse order
13:     this.digits = new int[count];
14:     for (int k = 0, i = s.Length - 1; i >= 0; i--)
15:     {
16:         if (Char.IsDigit(s[i]))
17:         {
18:             this.digits[k] = s[i] - '0';
19:             k++;
20:         }
21:     }
22: }

Beispiel 1. Benutzerdefinierter Konstruktor der Klasse BigInteger.


Nach der Erzeugung eines BigInteger-Objekts an Hand einer Zeichenkette kommen wir gleich auf die entgegengesetzte Operation zu sprechen: Umwandlung eines BigInteger-Objekts in eine Zeichenkette durch die geerbte (und zu überschreibende) Basisklassenmethode ToString:

01: // overrides
02: public override String ToString()
03: {
04:     return this.ToString("8", null);
05: }
06: 
07: // implementation of interface 'IFormattable'
08: public String ToString(String format, IFormatProvider formatProvider)
09: {
10:     int blocks;
11:     if (format != null)
12:     {
13:         if (!Int32.TryParse(format, out blocks))
14:             blocks = 8;
15: 
16:         if (blocks <= 0)
17:             blocks = 8;
18:     }
19:     else
20:         blocks = 8;
21: 
22:     int linebreak = 0;
23:     StringBuilder tmp = new StringBuilder();
24:     if (!this.sign)
25:         tmp.Append("-");
26: 
27:     // append leading spaces, if necessary
28:     if (this.Cardinality > 3 * blocks)
29:     {
30:         if (this.Cardinality % 3 == 1)
31:             tmp.Append ((!this.sign) ? " " : "  ");
32:         else if (this.Cardinality % 3 == 2)
33:             tmp.Append((!this.sign) ? "" : " ");
34:         else if (this.Cardinality % 3 == 0)
35:             tmp.Append((!this.sign) ? Environment.NewLine : "");
36:     }
37: 
38: 
39:     for (int i = this.digits.Length - 1; i >= 0; i--)
40:     {
41:         tmp.Append((char)('0' + this.digits[i]));
42:         if (i > 0 && i % 3 == 0)
43:         {
44:             tmp.Append('.');
45:             linebreak++;
46:             if (linebreak % blocks == 0)
47:                 tmp.Append(Environment.NewLine);
48:         }
49:     }
50: 
51:     return tmp.ToString();
52: }

Beispiel 2. Überschreibung der Basisklassenmethode ToString.


Die ToString-Methode in Listing 2 (Zeile 2) verzweigt direkt in eine Überladung von ToString ab Zeile 8. Hier haben wir es mit dem Kontrakt der ToString-Methode in Bezug auf die Standardschnittstelle IFormattable zu tun. Im ersten Parameter format kann ein Formatspezifizierer übergeben werden – laut Aufgabenstellung muss diese Zeichenkette eine ganze Zahl repräsentieren, um die Anzahl der Dreiziffernblöcke pro Zeile festzulegen. Ihre Auswertung, inklusive einiger Unannehmlichkeiten (die TryParse-Methode setzt im Fehlerfall den Wert einer referenzierten int-Variablen auf den Wert 0 zurück), findet in den Zeilen 10 bis 20 statt. Die Zeilen 27 bis 36 widmen sich dem Umstand, mit wie vielen Leerzeichen der erste Dreiziffernblock aufzufüllen sind, wenn die Anzahl der Ziffern kein Vielfaches von Drei ist. Da auch noch ein mögliches Vorzeichen zu berücksichtigen ist, gewinnt der Sourcecode leider nicht gerade an Übersichtlichkeit.

Die noch fehlenden zwei (Konvertierungs-)Konstruktoren sind mit den nun vorhandenen Vorbereitungen mehr als trivial:

// type conversion c'tors
public BigInteger(int n) : this(n.ToString()) { }
public BigInteger(long n) : this(n.ToString()) { }

Laut Spezifikation besitzt die BigInteger-Klasse drei Eigenschaften Sign, Cardinality und IsNull, mehr hierzu in Listing 3:

01: // properties
02: public bool Sign
03: {
04:     get
05:     {
06:         return this.sign;
07:     }
08: }
09: 
10: public int Cardinality
11: {
12:     get
13:     {
14:         return this.digits.Length;
15:     }
16: }
17: 
18: public bool IsNull
19: {
20:     get
21:     {
22:         return this.digits.Length == 1 && this.digits[0] == 0;
23:     }
24: }

Beispiel 3. Eigenschaften Sign, Cardinality und IsNull der BigInteger-Klasse.


Die unären Operatoren + und -, also positives oder negatives Vorzeichen eines BigInteger-Objekts, wurden in der Aufgabenstellung nicht extra aufgeführt. In der korrekten Implementierung einer BigInteger-Klasse dürfen sie aber nicht fehlen:

// unary '+' and '-' operator
public static BigInteger operator+ (BigInteger a)
{
    return (BigInteger)a.Clone();
}

public static BigInteger operator- (BigInteger a)
{
    BigInteger tmp = (BigInteger)a.Clone();
    tmp.sign = !a.sign;
    return tmp;
}

Beide Operatoren + und - delegieren ihre Arbeit im wesentlichen an die Clone-Methode, BigInteger-Objekte sollten sinnvollerweise den Kontrakt mit der IClonable-Schnittstelle eingehen. Mit dem kleinen Umweg, das aktuelle Objekt durch eine Zeichenkette darzustellen (Methode ToString), kann Clone äußerst kurz implementiert werden:

// implementation of interface 'ICloneable'
public Object Clone()
{
    return new BigInteger(this.ToString());
}

Ein Synergieeffekt der Clone-Methode besteht darin, dass wir mit ihr eine sehr einfache Realisierung für den Absolutbetrag eines BigInteger-Objekts erhalten (Methode Abs):

public BigInteger Abs()
{
    BigInteger tmp = (BigInteger) this.Clone();
    tmp.sign = true;
    return tmp;
}

Damit sind wir beim Kernstück der BigInteger-Klasse angekommen, ihren arithmetischen Operatoren. Die Addition großer Zahlen entnehmen Sie bitte Listing 4:

01: public static BigInteger operator+ (BigInteger a, BigInteger b)
02: {
03:     // handle sign and change operation, if necessary
04:     if (a.Sign != b.Sign)
05:         return (a.Sign) ? a - b.Abs() : b - a.Abs();
06: 
07:     // allocate array
08:     int[] digits;
09:     if (a.Cardinality >= b.Cardinality)
10:         digits = new int[a.Cardinality + 1];
11:     else
12:         digits = new int[b.Cardinality + 1];
13: 
14:     // add numbers digit per digit
15:     int carry = 0;
16:     for (int i = 0; i < digits.Length; i++)
17:     {
18:         if (i < a.Cardinality)
19:             carry += a.digits[i];
20:         if (i < b.Cardinality)
21:             carry += b.digits[i];
22: 
23:         digits[i] = carry % 10;
24:         carry /= 10;
25:     }
26: 
27:     BigInteger tmp = new BigInteger(a.Sign, digits);
28:     tmp.RemoveLeadingZeros();
29:     return tmp;
30: }

Beispiel 4. Implementierung der Addition großer ganzer Zahlen.


Subtil in Listing 4 sind die zwei Zeilen 4 und 5: Nicht jede Addition zweier ganzer Zahlen ist in Wirklichkeit eine Addition. Ja nach Vorhandensein eines negativen Vorzeichens beim ersten oder zweiten Summanden kann auch eine Subtraktion vorliegen. Sollte dies der Fall sein, wird in Zeile 5 an diese weiterverzeigt, die Parameter werden bzgl. ihres Vorzeichens entsprechend angepasst.

 

Bei der Addition zweier ganzer Zahlen kann man nicht präzise von vorne herein entscheiden, aus wie vielen Ziffern das Resultat besteht. Man muss leider zunächst eine näherungsweise Festlegung treffen, in dem man die Länge des größeren Summanden zu Grunde legt und diese für einen möglichen Überlauf in der letzten Stelle noch um Eins vergrößert. In den Zeilen 16 bis 26 finden Sie die Umsetzung der in Abbildung 1.5 und Abbildung 1.6 beschrieben schulischen Addition vor. Da die Längenabschätzung des Resultat-Arrays digits in den Zeilen 9 bis 12 möglicherweise nicht ganz exakt war, können in dem digits-Array noch führende Nullen vorhanden sein. Diese werden in Zeile 28 durch einen Aufruf der RemoveLeadingZeros-Methode entfernt. Damit sind wir auch schon bei der Subtraktion angekommen, siehe Listing 5:

01: public static BigInteger operator- (BigInteger a, BigInteger b)
02: {
03:     // handle sign and change operation, if necessary
04:     if (a.Sign != b.Sign)
05:         return (a.Sign) ? a + b.Abs() : -(a.Abs() + b);
06: 
07:     if (a.Abs() < b.Abs())
08:         return (a.Sign) ? -(b - a) : b.Abs() - a.Abs();
09: 
10:     // create copy of minuend
11:     BigInteger tmp = (BigInteger)a.Clone();
12: 
13:     // traverse digits of subtrahend
14:     for (int i = 0; i < b.Cardinality; i++)
15:     {
16:         if (tmp.digits[i] < b.digits[i])
17:         {
18:             if (tmp.digits[i + 1] != 0)
19:             {
20:                 tmp.digits[i + 1]--;
21:                 tmp.digits[i] += 10;
22:             }
23:             else
24:             {
25:                 // preceding digit is zero, cannot borrow directly
26:                 int pos = i + 1;
27:                 while (tmp.digits[pos] == 0)
28:                     pos++;
29: 
30:                 // borrow indirectly
31:                 for (int k = pos; k >= i + 1; k--)
32:                 {
33:                     tmp.digits[k]--;
34:                     tmp.digits[k - 1] += 10;
35:                 }
36:             }
37:         }
38: 
39:         // subtract current subtraend digit from minuend digit
40:         tmp.digits[i] -= b.digits[i];
41:     }
42: 
43:     tmp.RemoveLeadingZeros();
44:     return tmp;
45: }

Beispiel 5. Implementierung der Subtraktion großer ganzer Zahlen.


Die Implementierung der Subtraktion ist im Vergleich zur Addition etwas länger geraten. Die Umsetzung des Entbündelungsverfahrens in den Zeilen 16 bis 22 (Listing 5) ist einfach nachvollziehbar. Kann die Ziffer des Subtrahenden nicht von der korrespondieren Ziffer des Minuenden abgezogen werden, ist etwas mehr Realisierungsaufwand erforderlich, siehe dazu die Zeilen 25 bis 36. Analog zur Addition kann auch bei einer Subtraktion der Fall vorliegen, dass diese in Wirklichkeit einer Addition entspricht. In Zeile 5 erfolgt ein Aufruf der entsprechenden Addition mit bereinigten Vorzeichen. Im anderen Fall lässt die Subtraktion sich auch durchführen, es sind nur Subtrahend und Minuend zu vertauschen und das Vorzeichen des Ergebnisses entsprechend anzupassen. Da das Entbündelungsverfahrens nur funktioniert, wenn der Subtrahend kleiner als der Minuend ist, muss auch dieser Fall noch berücksichtigt werden, siehe dazu die Zeilen 7 und 8 von Listing 5.

In Zeile 7 finden wir den <-Operators auf zwei BigInteger-Objekte angewendet vor. Damit sind wir bei der IComparable<BigInteger>-Schnittstelle angekommen. Ihre Implementierung (Listing 6) ist nicht nur als Abrundung der Klasse BigInteger zu sehen, die Subtraktion muss stets einen Größenvergleich von Subtrahend und Minuend durchführen:

01: // implementation of interface 'IComparable<BigInteger>'
02: public int CompareTo(BigInteger a)
03: {
04:     if (this.sign && !a.sign)
05:         return 1;
06:     if (!this.sign && a.sign)
07:         return -1;
08: 
09:     int order = 0;
10:     if (this.Cardinality < a.Cardinality)
11:     {
12:         order = -1;
13:     }
14:     else if (this.Cardinality > a.Cardinality)
15:     {
16:         order = 1;
17:     }
18:     else
19:     {
20:         for (int i = this.Cardinality - 1; i >= 0; i--)
21:         {
22:             if (this.digits[i] < a.digits[i])
23:             {
24:                 order = -1;
25:                 break;
26:             }
27:             else if (this.digits[i] > a.digits[i])
28:             {
29:                 order = 1;
30:                 break;
31:             }
32:         }
33:     }
34: 
35:     return (this.sign) ? order : -order;
36: }

Beispiel 6. Implementierung der Schnittstelle IComparable<BigInteger>.


Da die Ziffern einer großen Zahl intern im BigInteger-Objekt in der umgekehrten Reihenfolge abgelegt werden, ist in der for-Wiederholungsschleife von Listing 6 (Zeile 20) zu beachten, dass die Ziffern von der höchstwertigen bis hin zur niedrigstwertigen Ziffer verglichen werden.

Wir sind etwas vom Thema abgekommen, wir waren bei den arithmetischen Operatoren stehen geblieben und fahren in Listing 7 mit der Multiplikation fort:

01: public static BigInteger operator* (BigInteger a, BigInteger b)
02: {
03:     int[] digits = new int[a.Cardinality + b.Cardinality];
04: 
05:     int carry = 0;
06:     for (int i = 0; i < digits.Length; i++)
07:     {
08:         digits[i] = carry;
09: 
10:         for (int j = 0; j < b.Cardinality; j++)
11:             if (i - j >= 0 && i - j < a.Cardinality)
12:                 digits[i] += a.digits[i - j] * b.digits[j];
13: 
14:         carry = digits[i] / 10;
15:         digits[i] %= 10;
16:     }
17: 
18:     bool sign = (a.Sign == b.Sign) ? true : false;
19:     BigInteger tmp = new BigInteger(sign, digits);
20:     tmp.RemoveLeadingZeros();
21:     return tmp;
22: }

Beispiel 7. Implementierung der Multiplikation großer ganzer Zahlen.


Wie bei der Addition lässt sich auch bei der Multiplikation die Anzahl der Ziffern des Ergebnisses vor der Rechenoperation nicht ganz exakt bestimmen. Entsprechend legen wir in Zeile 3 ein Array mit der größtmöglichen Länge für die Ziffern an. Einen Strich durch diese Längenberechnung können uns führende Nullen im Ergebnis machen, in Zeile 20 dürfen wir deshalb auf den Aufruf von RemoveLeadingZeros nicht verzichten. Der *-Operator ermöglicht eine recht kurze und übersichtliche Realisierung der Methode Power:

public BigInteger Power(int exponent)
{
    if (exponent == 0)
        return new BigInteger(1);

    BigInteger result = (BigInteger)this.Clone();
    if (exponent == 1)
        return result;

    for (int i = 1; i < exponent; i++)
        result = result * this;
                   
    if (!this.sign && exponent % 2 == 1)
        result.sign = this.sign;

    return result;
}

Wir sind fast am Ziel angekommen, es fehlt nur noch die Division (Listing 8).

01: public static BigInteger operator/ (BigInteger a, BigInteger b)
02: {
03:     BigInteger remainder = new BigInteger();
04:     StringBuilder sbResult = new StringBuilder();
05: 
06:     // need positive divisor
07:     BigInteger bAbs = b.Abs();
08: 
09:     int pos = a.Cardinality - 1;
10:     while (pos >= 0)
11:     {
12:         // append next digit from dividend to temporary divisor
13:         int len = (remainder.IsNull) ? 1 : remainder.Cardinality + 1;
14:         int[] digits = new int[len];
15: 
16:         // copy old digits
17:         for (int k = 0; k < len - 1; k++)
18:             digits[k + 1] = remainder.digits[k];
19: 
20:         // fetch digit from dividend
21:         digits[0] = a.digits[pos];
22: 
23:         remainder = new BigInteger(true, digits);
24: 
25:         // divide current dividend with divisor
26:         int n = 0;
27:         while (bAbs <= remainder)
28:         {
29:             n++;
30:             remainder -= bAbs;
31:         }
32:         sbResult.Append(n.ToString());
33: 
34:         // fetch next digit from divisor
35:         pos--;
36:     }
37: 
38:     BigInteger result = new BigInteger(sbResult.ToString());
39:     result.sign = (a.Sign == b.Sign) ? true : false;
40:     result.RemoveLeadingZeros();
41:     return result;
42: }

Beispiel 8. Implementierung der Divison großer ganzer Zahlen.


Das Ergebnis einer Division wird, wie in Abbildung 1.11 beschrieben, Ziffer für Ziffer berechnet. Aus diesem Grund bemühen wir in den Zeilen 4 und 32 ein StringBuilder-Objekt, das die einzelnen Ziffern aufnimmt. In Zeile 38 können wir den Konvertierungsoperator mit dem Klassentyp String als Eingangsparameter anwenden, um das Ergebnis in ein BigInteger zu wandeln. Das Spiegelstück der Divison, die Division mit Rest, führt uns zum Modulo-Operator % in Listing 9:

01: public static BigInteger operator% (BigInteger a, BigInteger b)
02: {
03:     return a - b * (a / b);  
04: }

Beispiel 9. Implementierung der Divison mit Rest (Modulo) großer ganzer Zahlen.


Es sind noch einige Restarbeiten zu erledigen, wie etwa die Betrachtung der unären Operatoren ++ und -- sowie der (expliziten) Konvertierungsoperatoren vom BigInteger-Klassentyp hin zu den elementaren Typen int bzw. long (Listing 10):

01: // type conversion operators
02: public static explicit operator long (BigInteger a)
03: {
04:     long n = 0;
05:     for (int i = 0; i < a.digits.Length; i++)
06:         n = (long) 10 * n + (long)a.digits[i];
07:     return n;
08: }
09: 
10: public static explicit operator int (BigInteger a)
11: {
12:     long n = (long) a;
13:     return (int) n;
14: }
15: 
16: // unary increment and decrement operator ('++' / '--')
17: public static BigInteger operator++ (BigInteger a)
18: {
19:     BigInteger tmp = (BigInteger)a.Clone();
20:     return tmp + 1;
21: }
22: 
23: public static BigInteger operator-- (BigInteger a)
24: {
25:     BigInteger tmp = (BigInteger)a.Clone();
26:     return tmp - 1;
27: }

Beispiel 10. Explizite Konvertierungsoperatoren, Inkrement- und Dekrement-Operator.


Nicht fehlen sollte die Methode RemoveLeadingZeros in unseren Betrachtungen. Sie kommt in der Realisierung der diversen Methoden und Operatoren der BigInteger-Klasse häufig zum Einsatz (Listing 11):

01: private void RemoveLeadingZeros()
02: {
03:     // count leading zeros
04:     int zeros = 0;
05:     for (int i = this.digits.Length - 1; i >= 0; i--)
06:     {
07:         if (this.digits[i] == 0)
08:         {
09:             zeros++;
10:         }
11:         else
12:             break;
13:     }
14: 
15:     // remove leading zeros
16:     if (zeros > 0)
17:     {
18:         if (zeros < this.digits.Length)
19:         {
20:             int[] tmp = new int[this.digits.Length - zeros];
21: 
22:             for (int i = 0; i < this.digits.Length - zeros; i++)
23:                 tmp[i] = this.digits[i];
24: 
25:             this.digits = tmp;
26:         }
27:         else
28:         {
29:             // create number '0'
30:             this.digits = new int[1];
31:             this.digits[0] = 0;
32:         }
33:     }
34: }

Beispiel 11. Methode RemoveLeadingZeros.


Damit sind am Ende der Lösungsbesprechung angekommen. Welchen Nutzen können wir aus der Klasse BigInteger ziehen? Wir demonstrieren als Beispiel die Fakultätfunktion aus der Mathematik, die jeder Zahl das Produkt aller natürlichen Zahlen kleiner und gleich dieser Zahl zuordnet. Als Notation wird der natürlichen Zahl ein Ausrufezeichen ! nachgestellt, also

n! = 1 * 2 * 3 * ... * n

Beim Berechnen der Fakultät stellen wir fest, dass diese, selbst für vergleichsweise kleine Argumente, schnell einen sehr großen Wert annimmt. Wir können das an einer Methode Faculty in C# ausprobieren, die wir auf Basis des Datentyps long definieren:

private static long Faculty(long n)
{
    if (n == 1)
        return 1;
    else
        return n * Faculty(n - 1);
}

Mit dieser Methode Faculty machen wir die Beobachtung, dass wir nur für Argumente n kleiner-gleich 20 ein korrektes Resultat erhalten:

Faculty of  1: 1
Faculty of  2: 2
Faculty of  3: 6
Faculty of  4: 24
Faculty of  5: 120
Faculty of  6: 720
Faculty of  7: 5040
Faculty of  8: 40320
Faculty of  9: 362880
Faculty of 10: 3628800
Faculty of 11: 39916800
Faculty of 12: 479001600
Faculty of 13: 6227020800
Faculty of 14: 87178291200
Faculty of 15: 1307674368000
Faculty of 16: 20922789888000
Faculty of 17: 355687428096000
Faculty of 18: 6402373705728000
Faculty of 19: 121645100408832000
Faculty of 20: 2432902008176640000
Faculty of 21: -4249290049419214848
Faculty of 22: -1250660718674968576

Ab dem Argument n = 21 werden die Resultate falsch, wie sich an dem negativen Vorzeichen leicht erkennen lässt. Für die Berechnung haben wir die rekursive Formel der Fakultätfunktion verwendet (Abbildung 1), was aber für die Falschheit der Ergebnisse nicht der Grund ist:

Rekursive Definition der Fakultätfunktion.

Abbildung 1. Rekursive Definition der Fakultätfunktion.


Mit den regulären Sprachmitteln von C# kommen wir jetzt nicht weiter, der Wertebereich des Datentyps long lässt einfach keine größeren Zahlen zu. Ersetzen wir in der Methode Faculty den Datentyp long durch BigInteger, so können wir die Fakultät korrekt für beliebig große Argumente berechnen:

public static BigInteger Faculty(BigInteger n)
{
    if (n == 1)
        return 1;
    else
        return n * Faculty(n - 1);
}

Mit folgendem Testrahmen sehen die ersten dreißig Fakultäten so aus:

public static void Test_Faculty (int max)
{
    for (int i = 1; i < max; i++)
    {
        BigInteger f = Faculty((BigInteger) i);
        Console.WriteLine("Faculty of {0,2}: {1:16}", i, f);
    }
}

Ausgabe (für max gleich 31):

Faculty of  1: 1
Faculty of  2: 2
Faculty of  3: 6
Faculty of  4: 24
Faculty of  5: 120
Faculty of  6: 720
Faculty of  7: 5.040
Faculty of  8: 40.320
Faculty of  9: 362.880
Faculty of 10: 3.628.800
Faculty of 11: 39.916.800
Faculty of 12: 479.001.600
Faculty of 13: 6.227.020.800
Faculty of 14: 87.178.291.200
Faculty of 15: 1.307.674.368.000
Faculty of 16: 20.922.789.888.000
Faculty of 17: 355.687.428.096.000
Faculty of 18: 6.402.373.705.728.000
Faculty of 19: 121.645.100.408.832.000
Faculty of 20: 2.432.902.008.176.640.000
Faculty of 21: 51.090.942.171.709.440.000
Faculty of 22: 1.124.000.727.777.607.680.000
Faculty of 23: 25.852.016.738.884.976.640.000
Faculty of 24: 620.448.401.733.239.439.360.000
Faculty of 25: 15.511.210.043.330.985.984.000.000
Faculty of 26: 403.291.461.126.605.635.584.000.000
Faculty of 27: 10.888.869.450.418.352.160.768.000.000
Faculty of 28: 304.888.344.611.713.860.501.504.000.000
Faculty of 29: 8.841.761.993.739.701.954.543.616.000.000
Faculty of 30: 265.252.859.812.191.058.636.308.480.000.000