Inhaltsverzeichnis
Ganzzahl : Implementierung beliebig genauer Ganzzahlen
Roll yer own
if you can't buy a ready made
if you won't be satisfied
when you feel a sudden need to unwind— Jethro Tull [Catfish Rising 1991]
Die Überlegungen zur Implementierung der Klasse Ganzzahl werden hier (endlich) umgesetzt.
Vorbereitungen
//: ganzzahl.cpp : Ganzzahlen beliebiger Genauigkeit - R.Richter 2004-09-26 /////////////////////////////////////////////////////////////////////////// // Abhängigkeiten #include <algorithm> // swap(), fill(), copy(), min(), max() #include <cassert> #include <cstdio> // sprintf() #include <cctype> // isdigit() #include "ganzzahl.h"
Es gab einmal Compiler-Hersteller, welche die std-Bibliothek absichtlich unvollständig ließen, um eigene Makrodefinitionen beizubehalten. Auch auf solchen sagenhaften Systemen soll dieses Modul nutzbar sein.
#if defined( _MSC_VER ) && _MSC_VER < 1300 /* Microsoft Visual C++ 6.0 */ namespace std { template <class T> inline T const& min(T const& x, T const& y) { return x < y ? x : y; } template <class T> inline T const& max(T const& x, T const& y) { return y < x ? x : y; } } #endif // _MSC_VER < 1300
Nach solchen Rücksichten werden zuerst jene Teile festgelegt, die nur innerhalb dieser Datei sichtbar sein sollen. Der hier beginnende unbenannte Namensraum verbirgt all diese Definitionen vor Zugriffen von außen und verhindert Kollisionen mit gleichnamigen Bezeichnern in anderen Modulen.
namespace { // Typen und Konstanten // Annahme: 2*sizeof(short) <= sizeof(long) // Gibt es Maschinen, auf denen das nicht erfüllt ist? typedef unsigned short Ziffer; typedef unsigned long Doppelziffer; unsigned const BITS = 8*sizeof(Ziffer); // Doppelziffer const BASIS = 10; Doppelziffer const BASIS = 1L << BITS; // Zweierpotenz Ziffer const MAXZIFFER = Ziffer(BASIS-1);
Wie im gewohnten kleinen 1x1 sind die Zwischenergebnisse
beim Rechnen mit einstelligen Zahlen manchmal zweistellig,
d.h. doppelt so breit wie die Ziffern.
Beim exakten Rechnen dürfen keine Wertbereichsüberschreitungen auftreten.
Der größtmögliche Ganzzahltyp für die Doppelziffer
begrenzt damit den möglichen Wertebereich für die Ziffern.
Manche Compiler beherrschen inzwischen Datentypen
long long
oder int64_t
(Standard C ISO 9899:1999).
Auf deren Einsatz wurde jedoch verzichtet,
um die Bibliothek portabel zu halten.
Datenorganisation
Der interne Aufbau der Datenstruktur
Aus den Hinweisen sind die notwendigen Strukturkomponenten zu entnehmen. Für die Ziffernfolge wird vorerst nur das Minimum, eine Ziffer, vorgesehen. Diese wird jedoch als Feld deklariert, um weitere Ziffern ansprechen zu können. Die höherwertigen Ziffern werden an diesen Datenkopf angehangen. Dabei wird ganz bewusst über das Ende des Strukturblockes hinaus adressiert. Die Speicherverwaltung wird sich darum kümmern müssen, dass dieser Bereich auch tatsächlich vorhanden ist und keine anderen Daten an diesen Stellen überschrieben werden.
// Blockanfang Blockende allokierter Speicher // | | | // v v v // | Kopfinformation | z[0] .............. z[reserviert-1] | struct Daten { unsigned referenzen; unsigned reserviert; unsigned laenge; bool negativ; Ziffer ziffer[1]; }; // Die Annahme: (char*) &negativ < (char*) &ziffern[i] für i>=0 // ist etwas riskant: Was, wenn Komponenten anders angeordnet werden? // Unbekannt: Gibt es Compiler, die aufeinanderfolgende Komponenten // nicht mit aufsteigenden Speicheradressen anlegen? // Unklar: Wie soll man das beim Übersetzen testen?
Diese (schmutzige) Technik ist nichts für schwache Nerven.
Da ihr Einsatz jedoch in diesem Modul gekapselt ist, besteht Aussicht auf Erfolg.
Ein dynamischer Zeiger auf die Ziffern oder ein std::vector<Ziffer>
statt eines Feldes wäre eine saubere Lösung,
jedoch mit einer zusätzlichen Allokationsanforderung und Freigabe
und mit zusätzlichem Speicherbedarf für den Zeiger.
Grenzen der Implementierung (auf einem 32Bit-System) sind:
- eine Zahl bis zu 4 Mrd. mal referenzieren (vorher wird woanders Speicher alle: die Zeiger),
- eine Zahl bis zu 4 GB lang (soviel Speicher steht wohl nicht zur Verfügung).
Alles kommt aus Null und Eins
Null und Eins, die ausgezeichneten Elemente der Addition und Multiplikation, werden als Initialwert und für Inkrementoperationen so häufig benutzt. Für diese Werte besondere Instanzen bereit zu halten, lohnt sich im Hinblick auf Speicher- und Laufzeiteffizienz. Diese Zahlenwerte gibt es also stets mindestens einmal.
Daten* null() { static Daten nullwert = { 1, 1, 1, false, 0 }; return &nullwert; } Daten* eins() { static Daten einswert = { 1, 1, 1, false, 1 }; return &einswert; }
Statt globaler Variablen wird das "Singleton pattern" [GoF] eingesetzt. Die Initialisierungsfolge globaler Variablen über Modulgrenzen hinweg ist nicht bestimmbar. Werden in anderen Modulen Ganzzahlen z.B. mit Null initialisiert, muss deren Referenzzähler schon initialisiert worden sein. Ansonsten führen Destruktoraufrufe am Programmende dann zu fehlerhaften dynamischen Freigaben des statischen Speichers globaler Variablen. Um das zu verhindern, werden die Zahlenwerte als lokal statische Variablen angelegt. Diese werden beim ersten Funktionsaufruf initialisiert. Die Rückgabe liefert stets einen gültigen Zeiger auf einen initialisierten Wert.
Die Zeiger müssen wegen der Referenzzählung Schreibzugriffe auf referenzen
erlauben.
Speicherverwaltung
Datenblöcke müssen angelegt, kopiert und freigegeben werden.
// Block anlegen, der mind. ziffern Platz hat, mit Nullen füllen Daten* anlegen(unsigned ziffern) { unsigned Ziffer constN_JE_BLOCK = sizeof(Daten)/sizeof(Ziffer); unsigned extrablocks = (ziffern-1 + ZIFFERN_JE_BLOCK-1)/ZIFFERN_JE_BLOCK; unsigned maxziffern = 1 + extrablocks * ZIFFERN_JE_BLOCK; Daten* p = (Daten*) new char[(1+extrablocks)*sizeof(Daten)]; p->referenzen = 0; p->reserviert = maxziffern; p->negativ = false; p->laenge = ziffern; std::fill(p->ziffer, p->ziffer + ziffern, Ziffer(0)); return p; } void freigeben(Daten* p) { assert(p != null()); assert(0 == p->referenzen); delete [] (char*)p; } void kopieren(Daten*& ziel, Daten const* quelle) { assert(ziel->reserviert >= quelle->laenge); ziel->laenge = quelle->laenge; ziel->negativ = quelle->negativ; std::copy(quelle->ziffer, quelle->ziffer + quelle->laenge, ziel->ziffer); }
Referenzzählung
Bei der Übernahme eines Datenblockzeigers wird der Referenzzähler erhöht. Bei jeder Freigabe wird der Referenzzähler abgesenkt, und falls es der letzte Verweis war, der Speicher freigegeben. Schreibzugriffe müssen so erfolgen, dass wirklich nur ein einzelner Wert verändert wird. Verweisen mehrere Zeiger auf den Datenblock, wird ein neuer Datenblock mit gleichen Inhalten erzeugt (lazy copying) und dann auf diesem gearbeitet (unique = einzig, einzeln).
void einklinken(Daten*& ziel, Daten* quelle) { ++ (ziel=quelle)->referenzen; } void ausklinken(Daten* p) { if (0 == -- p->referenzen) { freigeben(p); } } Daten*& uniq(Daten*& p) { if (p->referenzen > 1) { Daten* neu = anlegen(p->laenge); kopieren(neu, p); ausklinken(p); einklinken(p, neu); } return p; }
Wachsen und Schrumpfen
Bei manchen Rechenoperationen entstehen größere Zahlen. Stehen die neuen Stellen nicht innerhalb des reservierten Blockes zur Verfügung, wird ein neuer Datenblock angelegt und der Inhalt übernommen. Höherwertige Stellen (führende Ziffern) werden mit Nullen aufgefüllt.
void reservieren(Daten*& p, unsigned ziffern) { if (ziffern > p->reserviert) { Daten* neu = anlegen(ziffern); kopieren(neu, p); ausklinken(p); einklinken(p, neu); } if (p->laenge < ziffern) { std::fill(p->ziffer + p->laenge, p->ziffer + ziffern, Ziffer(0)); p->laenge = ziffern; } }
Am Ende von Rechenoperationen lassen sich führende Nullen eliminieren,
evtl. entsteht null()
.
void schrumpfen(Daten*& p) { assert(p->referenzen == 1); unsigned& len = p->laenge; Ziffer* z = p->ziffer; while (len > 1) { if (z[len-1] != 0) return; len --; } // len == 1 if (z[0] == 0 && p != null()) { ausklinken(p); einklinken(p, null()); } }
Rechenoperationen
Dafür war das ganze Brimborium nötig.
Vergleiche und Vorzeichenänderung
Welche Zahl hat den kleineren Absolutbetrag? Offensichtlich die mit weniger Ziffern. Bei gleicher Ziffernzahl entscheidet ein lexikographischer Vergleich, beginnend mit der höchstwertigen Ziffer. Ob und wie herum der Absolutvergleich ausgeführt werden muss, hängt vom Vorzeichen ab.
bool abs_kleiner(Daten const* x, Daten const* y) { if (x->laenge != y->laenge) return x->laenge < y->laenge; // bei gleicher Länge erster Unterschied unsigned i = x->laenge; while (i-- > 0) { if (x->ziffer[i] != y->ziffer[i]) { return x->ziffer[i] < y->ziffer[i]; } } return false; /* // von hinten nach vorn std::reverse_iterator<Ziffer const*> x1( x->ziffer + x->laenge ), x2( x->ziffer ), y1( y->ziffer + y->laenge ), y2( y->ziffer ); return std::lexicographical_compare(x1, x2, y1, y2); */ } bool kleiner(Daten const* x, Daten const* y) { if (x->negativ != y->negativ) return x->negativ; // gleiche Vorzeichen return x->negativ ? abs_kleiner(y, x) : abs_kleiner(x, y); }
Alle Zahlen außer Null lassen sich mit dem entgegengesetzten Vorzeichen versehen.
void neg(Daten*& p) { if (p != null()) { p->negativ = !p->negativ; } }
Strichrechnung
Der Algorithmus zum Addieren und der Algorithmus zum Subtrahieren werden in einer Funktion zusammengefasst. Die Vorzeichen regeln, welche der beiden Operationen auszuführen ist.
void add(Daten*& x, Daten const* y) { unsigned m = x->laenge; unsigned n = y->laenge; unsigned max_mn = std::max(m, n); if (x->negativ == y->negativ) // bei gleichen Vorzeichen addieren { reservieren(x, max_mn + 1); Ziffer* summe = x->ziffer; Ziffer const* u = x->ziffer; Ziffer const* v = y->ziffer; Doppelziffer uebertrag = 0; for (unsigned i=0; i < max_mn; ++i) { if (i < m) uebertrag += u[i]; if (i < n) uebertrag += v[i]; summe[i] = Ziffer(uebertrag % BASIS); uebertrag /= BASIS; } summe[max_mn] = Ziffer(uebertrag % BASIS); } else // bei unterschiedlichen Vorzeichen subtrahieren { reservieren(x, max_mn); Ziffer* differenz = x->ziffer; Ziffer const* u = x->ziffer; // Minuend Ziffer const* v = y->ziffer; // Subtrahend if (abs_kleiner(x, y)) { std::swap(u, v); std::swap(m, n); x->negativ = y->negativ; // Vorzeichen vom absolut größeren } Doppelziffer uebertrag = 1; // geborgt for (unsigned i=0; i < max_mn; ++i) { uebertrag += MAXZIFFER; if (i < m) uebertrag += u[i]; if (i < n) uebertrag -= v[i]; differenz[i] = Ziffer(uebertrag % BASIS); uebertrag /= BASIS; } assert(uebertrag == 1); // muss übrig bleiben, sonst war u<v } schrumpfen(x); }
Punktrechnung
Der Algorithmus zum Malnehmen ist bestechend einfach.
void mul(Daten*& x, Daten const* y) { unsigned m = x->laenge; unsigned n = y->laenge; Daten* p = anlegen(m+n); if (x->negativ != y->negativ) neg(p); Ziffer* produkt = p->ziffer; Ziffer const* u = x->ziffer; Ziffer const* v = y->ziffer; for (unsigned j=0; j < n; ++j) { if (v[j] != 0) { Doppelziffer uebertrag = 0; for (unsigned i=0; i < m; ++i) { uebertrag += produkt[i+j]; uebertrag += Doppelziffer(u[i])*v[j]; produkt[i+j] = Ziffer(uebertrag % BASIS); uebertrag /= BASIS; } produkt[m+j] = Ziffer(uebertrag % BASIS); } } ausklinken(x); einklinken(x, p); schrumpfen(x); }
void einstellige_division(Daten* q, Ziffer teiler, Ziffer& rest) { assert(teiler != 0); Ziffer* u = q->ziffer; unsigned i = q->laenge; Doppelziffer uebertrag = 0; while (i-- > 0) { uebertrag *= BASIS; uebertrag += u[i]; u[i] = Ziffer(uebertrag/teiler); uebertrag %= teiler; } rest = Ziffer(uebertrag%BASIS); }
und Malnehmen mit einer Ziffer
void einstellige_multiplikation(Daten* x, Ziffer faktor) { unsigned m = x->laenge; Ziffer* u = x->ziffer; Doppelziffer uebertrag = 0; for (unsigned i=0; i < m; ++i) { uebertrag += Doppelziffer(u[i]) * faktor; u[i] = Ziffer(uebertrag % BASIS); uebertrag /= BASIS; } assert(uebertrag == 0); }
sind Hilfsprozeduren für das mehrstellige Teilen, dessen Algorithmus jetzt implementiert wird.
void div(Daten*& q, Daten*& r, Daten const* x, Daten const* y) { if (y == null()) throw Ganzzahl::Nulldivision(); assert(q == null()); // Vorbedingung Aufruf: assert(r == x); // noch nicht vereinzelt if (abs_kleiner(x, y)) return; // q = 0, r = x if (y->laenge == 1) // einstellige Division { std::swap(uniq(q), uniq(r)); einstellige_division(q, y->ziffer[0], r->ziffer[0]); r->negativ = x->negativ; } else // mehrstellige Division { // Lit: [TAOCP2] Donald E. Knuth: // The Art of Computer Programming. Vol. 2, pp. 270--275 unsigned n = y->laenge; unsigned m = x->laenge - n; reservieren(uniq(q), m + 1); reservieren(uniq(r), n + m + 1); Daten* t; einklinken(t, anlegen(n)); // lokale Kopie, am Ende wieder freigeben kopieren(t, y); // weil y const Ziffer* u = r->ziffer; Ziffer* v = t->ziffer; Ziffer* quot = q->ziffer; // normalisieren Ziffer skalierungsfaktor = BASIS / (1 + v[n-1]); if (skalierungsfaktor > 1) { einstellige_multiplikation(r, skalierungsfaktor); einstellige_multiplikation(t, skalierungsfaktor); } // teilen Ziffer v1 = v[n-1]; Ziffer v2 = v[n-2]; for (unsigned j = m+1; j-- >0; ) { // schätze nächste Ziffer des Quotienten // quot[j] <= qhat <= quot[j]+2 Doppelziffer u12 = Doppelziffer(u[j+n]) * BASIS + u[j+n-1]; Doppelziffer qhat = u12 / v1; Doppelziffer rhat = u12 % v1; if (qhat == BASIS || qhat*v2 > BASIS * rhat + u[j+n-2]) { qhat--; // 1. Nachkorrektur rhat += v1; if (rhat < BASIS && qhat*v2 > BASIS * rhat + u[j+n-2]) { qhat--; // 2. Nachkorrektur } } // nun ist qhat = q[j] fast immer korrekt // multipliziere und ziehe ab Doppelziffer uebertrag = 1; // borgen Doppelziffer prod = 0; for (unsigned i=0; i < n; ++i) { prod += qhat * v[i]; uebertrag += (BASIS-1) + u[j+i] - prod % BASIS; u[j+i] = Ziffer(uebertrag % BASIS); uebertrag /= BASIS; prod /= BASIS; } // vorderste Ziffer uebertrag += (BASIS-1) + u[j+n] - prod % BASIS; u[j+n] = Ziffer(uebertrag % BASIS); uebertrag /= BASIS; if (uebertrag == 0) { qhat--; // doch zuviel weggenommen for (unsigned i=0; i < n; ++i) // zurückaddieren { uebertrag += u[j+i]; uebertrag += v[i]; u[j+i] = Ziffer(uebertrag % BASIS); uebertrag /= BASIS; } u[j+n] = 0; } // Ziffer festhalten quot[j] = Ziffer(qhat); } ausklinken(t); // denormalisieren if (skalierungsfaktor > 1) { Ziffer rest = 0; einstellige_division(r, skalierungsfaktor, rest); assert(rest == 0); } } // Vorzeichenregelung if (x->negativ != y->negativ) neg(q); assert( x->negativ == r->negativ ); schrumpfen(q); schrumpfen(r); // Nachbedingung: q = x/y, r = x%y oder x == q*y + r } } // namespace
Damit sind alle Hilfsfunktionen definiert und der anonyme Namensraum geschlossen.
Es ist jedoch Zeit zu bekennen,
dass die Typen char*
und Daten*
nicht wirklich kompatibel sind.
Jetzt kommt die schmutzigste Aufgabe, die Verbindung dieser beiden Typen herzustellen.
Mit einem Typecast wird die Typprüfung des Compilers ausgeschaltet.
Zwei Makros vereinfachen die Schreibarbeit,
allerdings nur wenn man wirklich weiß, was man hier tut…
#define D(p) (reinterpret_cast<Daten*&> (p)) #define ConstD(p) (reinterpret_cast<Daten* const> (p))
Die Unterscheidung in konstante Zeiger und nichtkonstante Zeiger-Referenzen ist subtil. Nicht konstante Zeiger müssen auch zurückgeschrieben werden können, deshalb Zeiger-Referenzen. Zeiger allein genügen hier nicht. (Der Versuch führt zu Compilerwarnungen über temporäre Objekte und Programmabsturz!)
Die Datenblöcke von konstanten Ganzzahlen können nicht vollständig konstant sein. Bei einer Zuweisung beispielsweise erhöht sich die Zahl der Referenzen. Dies ist möglich, da bei konstanten Objekten, die Zeigerattribute enthalten, zwar die Zeiger unveränderlich bleiben müssen, die Inhalte jener Datenblöcke aber trotzdem geändert werden können.
In der Nachbetrachtung wäre mutable unsigned referenzen
in der Struktur Daten
sinnvoll gewesen.
Dennoch wäre damit ein Problem nicht gelöst.
Der Compiler erlaubt nicht,
einen Zeiger mit Schreibrechten auf eine Adresse zu richten,
die aus einem Zeiger mit Nur-Lese-Rechten auf konstante Daten kommt,
sofern man keinen Typecast anwendet.
Genau das wäre dann beim Einklinken erforderlich.
Klar?
Wer damit Schwierigkeiten hat, verdeutliche sich bitte den sprachlichen Unterschied:
konstanter Zeiger auf Daten (Daten* const
),
Zeiger auf konstante Daten (Daten const*
),
konstanter Zeiger auf konstante Daten (Daten const* const
).
Ab hier folgen öffentliche Funktionen mit externer Bindung.
Methoden
Konstruktoren, Destruktor und Zuweisungsoperator
Hier findet die Referenzzählung statt.
Ganzzahl::Ganzzahl() { einklinken(D(p), null()); } Ganzzahl::Ganzzahl(Ganzzahl const& n) { einklinken(D(p), ConstD(n.p)); } Ganzzahl::~Ganzzahl() { ausklinken(D(p)); } Ganzzahl& Ganzzahl::operator=(Ganzzahl const& n) { if (this != &n) { ausklinken(D(p)); // this->~Ganzzahl(); einklinken(D(p), ConstD(n.p)); // new(this) Ganzzahl(n); } return *this; }
Konversion
Wechsel der Zahlenbasis zwischen Basis 10 und einer anderen erfolgen nach dem Horner-Schema:
Zahl n aus Ziffern (von vorn nach hinten)
geg: Ziffernfolge
n = 0
für jede Ziffern *= Basis
n += Ziffer
Ziffern aus einer Zahl (von hinten nach vorn)
geg: n >= 0
i = 0
WiederholeZiffer[i] = n % Basis
n /= Basissolange wie n != 0
entstandene Ziffernfolge umkehren
Basis kann dabei 10 oder auch eine andere sein.
Umwandlungen sind von und hin zu Zeichenketten und long
-Werten möglich.
Ganzzahl::Ganzzahl(long n) { unsigned Ziffer constN = // bei voller Ausnutzung der Binärziffern BASIS == (1L << 8*sizeof(Ziffer)) ? sizeof(long)/sizeof(Ziffer) // sonst im ungünstigsten Fall eine Ziffer je Bit (BASIS == 2) : 8*sizeof(long); einklinken(D(p), anlegen(ZIFFERN)); unsigned long u = n < 0 ? -n : n; for (unsigned i=0; u != 0; ++i) { assert(i < ZIFFERN); D(p)->ziffer[i] = u % BASIS; u /= BASIS; } if (n < 0) neg(D(p)); schrumpfen(D(p)); } Ganzzahl::Ganzzahl(std::string s) { Ganzzahl n, einer = 1, zehn = 10; bool vorzeichen = s.size() > 0 && s[0] == '-'; for (int i = vorzeichen; i < s.size(); ++i) { if (!isdigit(s[i])) break; D(einer.p)->ziffer[0] = s[i] - '0'; n *= zehn; n += einer; } if (vorzeichen) neg(D(n.p)); einklinken(D(p), ConstD(n.p)); } std::string Ganzzahl::to_string() const { Ganzzahl n = *this, zehn = 10; std::string s; do { Ganzzahl einer = n % zehn; s += char('0' + ConstD(einer.p)->ziffer[0]); n /= zehn; } while (ConstD(n.p) != null()); if (ConstD(p)->negativ) { s += '-'; } std::reverse(s.begin(), s.end()); return s; // Zum Debuggen ist die folgende Version hilfreich: /* char buf[20]; sprintf(buf, "(Basis %d)", BASIS); std::string s(buf); for (int i = ConstD(p)->laenge - 1; i >= 0; --i) { sprintf(buf, " %d", ConstD(p)->ziffer[i]); s += buf; } if (ConstD(p)->negativ) { s = "- " + s; } return s; */ } long Ganzzahl::to_long() const { long n = 0; bool minus = ConstD(p)->negativ; unsigned i = ConstD(p)->laenge; while (i-- > 0) { long alt = n; // fuer Überlaufprüfung n *= BASIS; if (minus) n -= ConstD(p)->ziffer[i]; else n += ConstD(p)->ziffer[i]; bool ueberlauf = minus && n > alt || !minus && n < alt; if (ueberlauf) throw Bereichsfehler(); } return n; }
Operatoren
Die Operatoren sind weiter nichts als Umhüllungen ("Wrapper") für die oben definierten Hilfsprozeduren.
// logische Null bool Ganzzahl::operator!() const { return ConstD(p) == null(); } // arithmetische Operationen Ganzzahl Ganzzahl::operator-() const { Ganzzahl n(*this); neg(uniq(D(n.p))); return n; } Ganzzahl& Ganzzahl::operator++() { add(uniq(D(p)), eins()); // *this += 1; return *this; } Ganzzahl& Ganzzahl::operator--() { neg(uniq(D(p))); add(D(p), eins()); neg(D(p)); return *this; // *this += -1; } Ganzzahl& Ganzzahl::operator+=(Ganzzahl const& n) { add(uniq(D(p)), ConstD(n.p)); return *this; } Ganzzahl& Ganzzahl::operator-=(Ganzzahl const& n) { neg(uniq(D(p))); add(D(p), ConstD(n.p)); neg(D(p)); return *this; // *this += -n; } Ganzzahl& Ganzzahl::operator*=(Ganzzahl const& n) { mul(uniq(D(p)), ConstD(n.p)); return *this; } Ganzzahl& Ganzzahl::operator/=(Ganzzahl const& n) { Ganzzahl quot, rest(*this); div(D(quot.p), D(rest.p), ConstD(p), ConstD(n.p)); std::swap(p, quot.p); return *this; } Ganzzahl& Ganzzahl::operator%=(Ganzzahl const& n) { Ganzzahl quot, rest(*this); div(D(quot.p), D(rest.p), ConstD(p), ConstD(n.p)); std::swap(p, rest.p); return *this; }
globale Funktionen
Der Kleiner-als-Operator ist nochmals simpel. Bei der Eingabe muss etwas sorgfältiger geprüft werden, welche Zeichen als Eingabe zulässig sind. Zwischen Minuszeichen und Ziffern darf kein Leerzeichen stehen.
bool operator<(Ganzzahl const& m, Ganzzahl const& n) { return kleiner(ConstD(m.p), ConstD(n.p)); } std::istream& operator>>(std::istream& is, Ganzzahl& n) { std::string s; // Die einfache Variante // is >> s; // if( is ) n = Ganzzahl(s); // funktioniert nur mit gültigen Eingaben, deshalb is >> std::ws; if (is.peek() == '-') s += is.get(); while (is && isdigit(is.peek())) { s += is.get(); } if (s.size() == 0 || s.size() == 1 && s[0] == '-') { if (s.size() == 1) is.putback('-'); is.setstate(std::ios_base::failbit); } else { n = Ganzzahl(s); } return is; }
Alle implementierten Funktionen sind zu testen.