anwenden:ganzzahl_cpp
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
— | anwenden:ganzzahl_cpp [2020-07-26 17:15] (aktuell) – angelegt - Externe Bearbeitung 127.0.0.1 | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
+ | ====== 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 | ||
+ | >> | ||
+ | |||
+ | |||
+ | Die [[anwenden: | ||
+ | zur Implementierung der | ||
+ | [[anwenden: | ||
+ | werden hier (endlich) umgesetzt. | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | ===== Vorbereitungen ===== | ||
+ | <code cpp> | ||
+ | //: ganzzahl.cpp : Ganzzahlen beliebiger Genauigkeit - R.Richter 2004-09-26 | ||
+ | /////////////////////////////////////////////////////////////////////////// | ||
+ | |||
+ | // Abhängigkeiten | ||
+ | #include < | ||
+ | #include < | ||
+ | #include < | ||
+ | #include < | ||
+ | #include " | ||
+ | |||
+ | </ | ||
+ | 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. | ||
+ | |||
+ | <code cpp> | ||
+ | #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. | ||
+ | |||
+ | <code cpp> | ||
+ | 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 | ||
+ | // Doppelziffer const BASIS = 10; | ||
+ | Doppelziffer const BASIS = 1L << BITS; // Zweierpotenz | ||
+ | Ziffer const | ||
+ | |||
+ | </ | ||
+ | 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 '' | ||
+ | begrenzt damit den möglichen Wertebereich für die Ziffern. | ||
+ | Manche Compiler beherrschen inzwischen Datentypen | ||
+ | '' | ||
+ | Auf deren Einsatz wurde jedoch verzichtet, | ||
+ | um die Bibliothek portabel zu halten. | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | ===== Datenorganisation ===== | ||
+ | ==== Der interne Aufbau der Datenstruktur ==== | ||
+ | Aus den [[ganzzahl_impl# | ||
+ | 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. | ||
+ | |||
+ | <code cpp> | ||
+ | // Blockanfang | ||
+ | // | | ||
+ | // v | ||
+ | // | Kopfinformation | z[0] .............. z[reserviert-1] | | ||
+ | |||
+ | struct Daten | ||
+ | { | ||
+ | unsigned referenzen; | ||
+ | unsigned reserviert; | ||
+ | unsigned laenge; | ||
+ | bool | ||
+ | Ziffer | ||
+ | }; | ||
+ | |||
+ | // Die Annahme: (char*) & | ||
+ | // 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 '' | ||
+ | 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. | ||
+ | |||
+ | <code cpp> | ||
+ | Daten* null() | ||
+ | { | ||
+ | static Daten nullwert = { 1, 1, 1, false, 0 }; | ||
+ | return & | ||
+ | } | ||
+ | |||
+ | Daten* eins() | ||
+ | { | ||
+ | static Daten einswert = { 1, 1, 1, false, 1 }; | ||
+ | return & | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | Statt globaler Variablen wird das " | ||
+ | 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 '' | ||
+ | |||
+ | ==== Speicherverwaltung ==== | ||
+ | Datenblöcke müssen angelegt, kopiert und freigegeben werden. | ||
+ | |||
+ | |||
+ | <code cpp> | ||
+ | // Block anlegen, der mind. ziffern Platz hat, mit Nullen füllen | ||
+ | |||
+ | Daten* anlegen(unsigned ziffern) | ||
+ | { | ||
+ | unsigned Ziffer constN_JE_BLOCK = sizeof(Daten)/ | ||
+ | unsigned extrablocks = (ziffern-1 + ZIFFERN_JE_BLOCK-1)/ | ||
+ | unsigned maxziffern | ||
+ | | ||
+ | Daten* p = (Daten*) new char[(1+extrablocks)*sizeof(Daten)]; | ||
+ | p-> | ||
+ | p-> | ||
+ | p-> | ||
+ | p-> | ||
+ | std:: | ||
+ | return p; | ||
+ | } | ||
+ | |||
+ | void freigeben(Daten* p) | ||
+ | { | ||
+ | assert(p != null()); | ||
+ | assert(0 == p-> | ||
+ | delete [] (char*)p; | ||
+ | } | ||
+ | |||
+ | void kopieren(Daten*& | ||
+ | { | ||
+ | assert(ziel-> | ||
+ | ziel-> | ||
+ | ziel-> | ||
+ | std:: | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | ==== 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). | ||
+ | |||
+ | <code cpp> | ||
+ | void einklinken(Daten*& | ||
+ | { | ||
+ | ++ (ziel=quelle)-> | ||
+ | } | ||
+ | |||
+ | void ausklinken(Daten* p) | ||
+ | { | ||
+ | if (0 == -- p-> | ||
+ | { | ||
+ | freigeben(p); | ||
+ | } | ||
+ | } | ||
+ | |||
+ | Daten*& uniq(Daten*& | ||
+ | { | ||
+ | if (p-> | ||
+ | { | ||
+ | Daten* neu = anlegen(p-> | ||
+ | kopieren(neu, | ||
+ | ausklinken(p); | ||
+ | einklinken(p, | ||
+ | } | ||
+ | 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. | ||
+ | |||
+ | <code cpp> | ||
+ | void reservieren(Daten*& | ||
+ | { | ||
+ | if (ziffern > p-> | ||
+ | { | ||
+ | Daten* neu = anlegen(ziffern); | ||
+ | kopieren(neu, | ||
+ | ausklinken(p); | ||
+ | einklinken(p, | ||
+ | } | ||
+ | if (p-> | ||
+ | { | ||
+ | std:: | ||
+ | p-> | ||
+ | } | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | Am Ende von Rechenoperationen lassen sich führende Nullen eliminieren, | ||
+ | evtl. entsteht '' | ||
+ | |||
+ | <code cpp> | ||
+ | void schrumpfen(Daten*& | ||
+ | { | ||
+ | assert(p-> | ||
+ | unsigned& | ||
+ | Ziffer* | ||
+ | |||
+ | while (len > 1) | ||
+ | { | ||
+ | if (z[len-1] != 0) return; | ||
+ | len --; | ||
+ | } | ||
+ | // len == 1 | ||
+ | if (z[0] == 0 && p != null()) | ||
+ | { | ||
+ | ausklinken(p); | ||
+ | einklinken(p, | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | ===== Rechenoperationen | ||
+ | Dafür war das ganze Brimborium nötig. | ||
+ | |||
+ | |||
+ | ==== Vergleiche und Vorzeichenänderung ==== | ||
+ | Welche Zahl hat den kleineren Absolutbetrag? | ||
+ | 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. | ||
+ | |||
+ | |||
+ | <code cpp> | ||
+ | bool abs_kleiner(Daten const* x, Daten const* y) | ||
+ | { | ||
+ | if (x-> | ||
+ | |||
+ | // bei gleicher Länge erster Unterschied | ||
+ | unsigned i = x-> | ||
+ | while (i-- > 0) | ||
+ | { | ||
+ | if (x-> | ||
+ | { | ||
+ | return x-> | ||
+ | } | ||
+ | } | ||
+ | return false; | ||
+ | /* | ||
+ | // von hinten nach vorn | ||
+ | std:: | ||
+ | x1( x-> | ||
+ | y1( y-> | ||
+ | | ||
+ | return std:: | ||
+ | */ | ||
+ | } | ||
+ | |||
+ | bool kleiner(Daten const* x, Daten const* y) | ||
+ | { | ||
+ | if (x-> | ||
+ | |||
+ | // gleiche Vorzeichen | ||
+ | return x-> | ||
+ | : abs_kleiner(x, | ||
+ | } | ||
+ | </ | ||
+ | Alle Zahlen außer Null lassen sich mit dem entgegengesetzten Vorzeichen versehen. | ||
+ | |||
+ | <code cpp> | ||
+ | void neg(Daten*& | ||
+ | { | ||
+ | if (p != null()) | ||
+ | { | ||
+ | p-> | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | |||
+ | |||
+ | ==== Strichrechnung ==== | ||
+ | Der [[anwenden: | ||
+ | und der [[anwenden: | ||
+ | werden in einer Funktion zusammengefasst. | ||
+ | Die Vorzeichen regeln, welche der beiden Operationen auszuführen ist. | ||
+ | |||
+ | <code cpp> | ||
+ | void add(Daten*& | ||
+ | { | ||
+ | unsigned m = x-> | ||
+ | unsigned n = y-> | ||
+ | unsigned max_mn = std::max(m, n); | ||
+ | |||
+ | if (x-> | ||
+ | { | ||
+ | reservieren(x, | ||
+ | |||
+ | Ziffer* summe = x-> | ||
+ | Ziffer const* u = x-> | ||
+ | Ziffer const* v = y-> | ||
+ | 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] | ||
+ | uebertrag /= BASIS; | ||
+ | } | ||
+ | summe[max_mn] = Ziffer(uebertrag % BASIS); | ||
+ | } | ||
+ | else // bei unterschiedlichen Vorzeichen subtrahieren | ||
+ | { | ||
+ | reservieren(x, | ||
+ | |||
+ | Ziffer* differenz = x-> | ||
+ | Ziffer const* u = x-> | ||
+ | Ziffer const* v = y-> | ||
+ | |||
+ | if (abs_kleiner(x, | ||
+ | { | ||
+ | std:: | ||
+ | std:: | ||
+ | x-> | ||
+ | } | ||
+ | |||
+ | 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 | ||
+ | } | ||
+ | assert(uebertrag == 1); // muss übrig bleiben, sonst war u<v | ||
+ | } | ||
+ | schrumpfen(x); | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | ==== Punktrechnung ==== | ||
+ | Der [[anwenden: | ||
+ | zum Malnehmen ist bestechend einfach. | ||
+ | |||
+ | |||
+ | <code cpp> | ||
+ | void mul(Daten*& | ||
+ | { | ||
+ | unsigned m = x-> | ||
+ | unsigned n = y-> | ||
+ | |||
+ | Daten* p = anlegen(m+n); | ||
+ | if (x-> | ||
+ | |||
+ | Ziffer* produkt = p-> | ||
+ | Ziffer const* u = x-> | ||
+ | Ziffer const* v = y-> | ||
+ | | ||
+ | for (unsigned j=0; j < n; ++j) | ||
+ | { | ||
+ | if (v[j] != 0) | ||
+ | { | ||
+ | Doppelziffer uebertrag = 0; | ||
+ | | ||
+ | for (unsigned i=0; i < m; ++i) | ||
+ | { | ||
+ | uebertrag | ||
+ | uebertrag | ||
+ | produkt[i+j] = Ziffer(uebertrag % BASIS); | ||
+ | uebertrag | ||
+ | } | ||
+ | produkt[m+j] = Ziffer(uebertrag % BASIS); | ||
+ | } | ||
+ | } | ||
+ | ausklinken(x); | ||
+ | einklinken(x, | ||
+ | schrumpfen(x); | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | [[anwenden: | ||
+ | |||
+ | <code cpp> | ||
+ | void einstellige_division(Daten* q, Ziffer teiler, Ziffer& rest) | ||
+ | { | ||
+ | assert(teiler != 0); | ||
+ | | ||
+ | Ziffer* | ||
+ | unsigned i = q-> | ||
+ | Doppelziffer uebertrag = 0; | ||
+ | | ||
+ | while (i-- > 0) | ||
+ | { | ||
+ | uebertrag *= BASIS; | ||
+ | uebertrag += u[i]; | ||
+ | u[i] = Ziffer(uebertrag/ | ||
+ | uebertrag %= teiler; | ||
+ | } | ||
+ | rest = Ziffer(uebertrag%BASIS); | ||
+ | } | ||
+ | </ | ||
+ | und | ||
+ | [[anwenden: | ||
+ | |||
+ | <code cpp> | ||
+ | void einstellige_multiplikation(Daten* x, Ziffer faktor) | ||
+ | { | ||
+ | unsigned m = 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 | ||
+ | [[anwenden: | ||
+ | jetzt implementiert wird. | ||
+ | |||
+ | <code cpp> | ||
+ | void div(Daten*& | ||
+ | { | ||
+ | if (y == null()) throw Ganzzahl:: | ||
+ | |||
+ | assert(q == null()); // Vorbedingung Aufruf: | ||
+ | assert(r == x); // noch nicht vereinzelt | ||
+ | | ||
+ | if (abs_kleiner(x, | ||
+ | | ||
+ | if (y-> | ||
+ | { | ||
+ | std:: | ||
+ | einstellige_division(q, | ||
+ | r-> | ||
+ | } | ||
+ | else // mehrstellige Division | ||
+ | { // Lit: [TAOCP2] Donald E. Knuth: | ||
+ | // The Art of Computer Programming. Vol. 2, pp. 270--275 | ||
+ | |||
+ | unsigned n = y-> | ||
+ | unsigned m = x-> | ||
+ | reservieren(uniq(q), | ||
+ | reservieren(uniq(r), | ||
+ | |||
+ | Daten* t; | ||
+ | einklinken(t, | ||
+ | kopieren(t, y); // weil y const | ||
+ | |||
+ | Ziffer* u = r-> | ||
+ | Ziffer* v = t-> | ||
+ | Ziffer* quot = q-> | ||
+ | |||
+ | // normalisieren | ||
+ | Ziffer skalierungsfaktor = BASIS / (1 + v[n-1]); | ||
+ | |||
+ | if (skalierungsfaktor > 1) | ||
+ | { | ||
+ | einstellige_multiplikation(r, | ||
+ | einstellige_multiplikation(t, | ||
+ | } | ||
+ | |||
+ | // 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--; | ||
+ | rhat += v1; | ||
+ | |||
+ | if (rhat < BASIS && qhat*v2 > BASIS * rhat + u[j+n-2]) | ||
+ | { | ||
+ | qhat--; | ||
+ | } | ||
+ | } | ||
+ | // 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] | ||
+ | uebertrag /= BASIS; | ||
+ | prod /= BASIS; | ||
+ | } | ||
+ | // vorderste Ziffer | ||
+ | uebertrag += (BASIS-1) + u[j+n] - prod % BASIS; | ||
+ | u[j+n] | ||
+ | uebertrag /= BASIS; | ||
+ | | ||
+ | if (uebertrag == 0) | ||
+ | { | ||
+ | qhat--; | ||
+ | for (unsigned i=0; i < n; ++i) // zurückaddieren | ||
+ | { | ||
+ | uebertrag += u[j+i]; | ||
+ | uebertrag += v[i]; | ||
+ | u[j+i] | ||
+ | uebertrag /= BASIS; | ||
+ | } | ||
+ | u[j+n] = 0; | ||
+ | } | ||
+ | // Ziffer festhalten | ||
+ | quot[j] = Ziffer(qhat); | ||
+ | } | ||
+ | ausklinken(t); | ||
+ | |||
+ | // denormalisieren | ||
+ | if (skalierungsfaktor > 1) | ||
+ | { | ||
+ | Ziffer rest = 0; | ||
+ | einstellige_division(r, | ||
+ | assert(rest == 0); | ||
+ | } | ||
+ | } | ||
+ | // Vorzeichenregelung | ||
+ | if (x-> | ||
+ | assert( x-> | ||
+ | |||
+ | schrumpfen(q); | ||
+ | schrumpfen(r); | ||
+ | // Nachbedingung: | ||
+ | } | ||
+ | |||
+ | } // namespace | ||
+ | |||
+ | </ | ||
+ | Damit sind alle Hilfsfunktionen definiert und der anonyme Namensraum geschlossen. | ||
+ | Es ist jedoch Zeit zu bekennen, | ||
+ | dass die Typen '' | ||
+ | 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... | ||
+ | |||
+ | <code cpp> | ||
+ | #define D(p) (reinterpret_cast< | ||
+ | #define ConstD(p) (reinterpret_cast< | ||
+ | |||
+ | </ | ||
+ | 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 '' | ||
+ | in der Struktur '' | ||
+ | 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 ('' | ||
+ | Zeiger auf konstante Daten ('' | ||
+ | konstanter Zeiger auf konstante Daten ('' | ||
+ | |||
+ | Ab hier folgen öffentliche Funktionen mit externer Bindung. | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | ===== Methoden ===== | ||
+ | ==== Konstruktoren, | ||
+ | Hier findet die Referenzzählung statt. | ||
+ | |||
+ | <code cpp> | ||
+ | Ganzzahl:: | ||
+ | { | ||
+ | einklinken(D(p), | ||
+ | } | ||
+ | |||
+ | Ganzzahl:: | ||
+ | { | ||
+ | einklinken(D(p), | ||
+ | } | ||
+ | |||
+ | Ganzzahl:: | ||
+ | { | ||
+ | ausklinken(D(p)); | ||
+ | } | ||
+ | |||
+ | Ganzzahl& | ||
+ | { | ||
+ | if (this != &n) | ||
+ | { | ||
+ | ausklinken(D(p)); | ||
+ | einklinken(D(p), | ||
+ | } | ||
+ | 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 Ziffer | ||
+ | >> | ||
+ | >> | ||
+ | |||
+ | Ziffern aus einer Zahl (von hinten nach vorn) | ||
+ | |||
+ | |||
+ | > geg: n >= 0 | ||
+ | > i = 0 | ||
+ | > Wiederhole | ||
+ | >> | ||
+ | >> | ||
+ | > solange wie n != 0 | ||
+ | > entstandene Ziffernfolge umkehren | ||
+ | |||
+ | Basis kann dabei 10 oder auch eine andere sein. | ||
+ | Umwandlungen sind von und hin zu Zeichenketten und '' | ||
+ | |||
+ | <code cpp> | ||
+ | Ganzzahl:: | ||
+ | { | ||
+ | unsigned Ziffer constN = | ||
+ | // bei voller Ausnutzung der Binärziffern | ||
+ | BASIS == (1L << 8*sizeof(Ziffer)) ? | ||
+ | sizeof(long)/ | ||
+ | // sonst im ungünstigsten Fall eine Ziffer je Bit (BASIS == 2) | ||
+ | : 8*sizeof(long); | ||
+ | einklinken(D(p), | ||
+ | |||
+ | unsigned long u = n < 0 ? -n : n; | ||
+ | |||
+ | for (unsigned i=0; u != 0; ++i) | ||
+ | { | ||
+ | assert(i < ZIFFERN); | ||
+ | D(p)-> | ||
+ | u /= BASIS; | ||
+ | } | ||
+ | |||
+ | if (n < 0) neg(D(p)); | ||
+ | schrumpfen(D(p)); | ||
+ | } | ||
+ | |||
+ | Ganzzahl:: | ||
+ | { | ||
+ | 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)-> | ||
+ | n *= zehn; | ||
+ | n += einer; | ||
+ | } | ||
+ | if (vorzeichen) neg(D(n.p)); | ||
+ | | ||
+ | einklinken(D(p), | ||
+ | } | ||
+ | |||
+ | std::string Ganzzahl:: | ||
+ | { | ||
+ | Ganzzahl n = *this, zehn = 10; | ||
+ | std::string s; | ||
+ | |||
+ | do | ||
+ | { | ||
+ | Ganzzahl einer = n % zehn; | ||
+ | s += char(' | ||
+ | n /= zehn; | ||
+ | } while (ConstD(n.p) != null()); | ||
+ | | ||
+ | if (ConstD(p)-> | ||
+ | { | ||
+ | s += ' | ||
+ | } | ||
+ | std:: | ||
+ | return s; | ||
+ | |||
+ | // Zum Debuggen ist die folgende Version hilfreich: | ||
+ | /* | ||
+ | char buf[20]; | ||
+ | sprintf(buf, | ||
+ | std::string s(buf); | ||
+ | for (int i = ConstD(p)-> | ||
+ | { | ||
+ | sprintf(buf, | ||
+ | s += buf; | ||
+ | } | ||
+ | if (ConstD(p)-> | ||
+ | { | ||
+ | s = "- " + s; | ||
+ | } | ||
+ | return s; | ||
+ | */ | ||
+ | } | ||
+ | |||
+ | long Ganzzahl:: | ||
+ | { | ||
+ | long n = 0; | ||
+ | bool minus = ConstD(p)-> | ||
+ | unsigned i = ConstD(p)-> | ||
+ | |||
+ | while (i-- > 0) | ||
+ | { | ||
+ | long alt = n; // fuer Überlaufprüfung | ||
+ | |||
+ | n *= BASIS; | ||
+ | if (minus) n -= ConstD(p)-> | ||
+ | else n += ConstD(p)-> | ||
+ | |||
+ | bool ueberlauf = minus && n > alt || | ||
+ | !minus && n < alt; | ||
+ | if (ueberlauf) throw Bereichsfehler(); | ||
+ | } | ||
+ | return n; | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | ==== Operatoren ==== | ||
+ | Die Operatoren sind weiter nichts als Umhüllungen (" | ||
+ | |||
+ | |||
+ | <code cpp> | ||
+ | // logische Null | ||
+ | bool Ganzzahl:: | ||
+ | { | ||
+ | return ConstD(p) == null(); | ||
+ | } | ||
+ | |||
+ | // arithmetische Operationen | ||
+ | Ganzzahl Ganzzahl:: | ||
+ | { | ||
+ | Ganzzahl n(*this); | ||
+ | neg(uniq(D(n.p))); | ||
+ | return n; | ||
+ | } | ||
+ | |||
+ | Ganzzahl& | ||
+ | { | ||
+ | add(uniq(D(p)), | ||
+ | return *this; | ||
+ | } | ||
+ | |||
+ | Ganzzahl& | ||
+ | { | ||
+ | neg(uniq(D(p))); | ||
+ | add(D(p), eins()); | ||
+ | neg(D(p)); | ||
+ | return *this; // *this += -1; | ||
+ | } | ||
+ | |||
+ | Ganzzahl& | ||
+ | { | ||
+ | add(uniq(D(p)), | ||
+ | return *this; | ||
+ | } | ||
+ | |||
+ | Ganzzahl& | ||
+ | { | ||
+ | neg(uniq(D(p))); | ||
+ | add(D(p), ConstD(n.p)); | ||
+ | neg(D(p)); | ||
+ | return *this; // *this += -n; | ||
+ | } | ||
+ | |||
+ | Ganzzahl& | ||
+ | { | ||
+ | mul(uniq(D(p)), | ||
+ | return *this; | ||
+ | } | ||
+ | |||
+ | Ganzzahl& | ||
+ | { | ||
+ | Ganzzahl quot, rest(*this); | ||
+ | div(D(quot.p), | ||
+ | std:: | ||
+ | return *this; | ||
+ | } | ||
+ | |||
+ | Ganzzahl& | ||
+ | { | ||
+ | Ganzzahl quot, rest(*this); | ||
+ | div(D(quot.p), | ||
+ | std:: | ||
+ | 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. | ||
+ | |||
+ | <code cpp> | ||
+ | bool operator< | ||
+ | { | ||
+ | return kleiner(ConstD(m.p), | ||
+ | } | ||
+ | |||
+ | std:: | ||
+ | { | ||
+ | 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() == ' | ||
+ | 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:: | ||
+ | } | ||
+ | else | ||
+ | { | ||
+ | n = Ganzzahl(s); | ||
+ | } | ||
+ | return is; | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | Alle implementierten Funktionen sind zu | ||
+ | [[anwenden: | ||
anwenden/ganzzahl_cpp.txt · Zuletzt geändert: 2020-07-26 17:15 von 127.0.0.1