namespace cpp {}

C++ lernen, kennen, anwenden

Benutzer-Werkzeuge

Webseiten-Werkzeuge


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
 +>>---  Jethro Tull [Catfish Rising 1991]
 +
 +
 +Die [[anwenden:ganzzahl_impl|Überlegungen]]
 +zur Implementierung der 
 +[[anwenden:ganzzahl|Klasse Ganzzahl]]
 +werden hier (endlich) umgesetzt. 
 +
 +
 +
 +
 +===== Vorbereitungen =====
 +<code cpp>
 +//: 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"
 +
 +</code>
 +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
 +
 +</code>
 +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     BITS      = 8*sizeof(Ziffer);
 +// Doppelziffer const BASIS  = 10;
 +Doppelziffer const BASIS     = 1L << BITS;  // Zweierpotenz
 +Ziffer const       MAXZIFFER = Ziffer(BASIS-1);
 +
 +</code>
 +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 [[ganzzahl_impl#Hinweise|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.
 +
 +<code cpp>
 +// Blockanfang             Blockende    allokierter Speicher
 +// |                                                     |
 +// 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? 
 +
 +</code>
 +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.
 +
 +<code cpp>
 +Daten* null()
 +{
 +  static Daten nullwert = { 1, 1, 1, false, 0 }; 
 +  return &nullwert;
 +}
 +
 +Daten* eins()
 +{
 +  static Daten einswert = { 1, 1, 1, false, 1 }; 
 +  return &einswert;
 +}
 +
 +</code>
 +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.
 +
 +
 +<code cpp>
 +// 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);
 +}
 +
 +</code>
 +==== 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, 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;
 +}
 +
 +</code>
 +==== 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*& 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; 
 +  }    
 +}    
 +
 +</code>
 +Am Ende von Rechenoperationen lassen sich führende Nullen eliminieren,
 +evtl. entsteht ''null()''.
 +
 +<code cpp>
 +void schrumpfen(Daten*& p)
 +{
 +  assert(p->referenzen == 1);  
 +  unsigned& len = p->laenge;
 +  Ziffer*     = 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());  
 +  }    
 +}
 +</code>
 +===== 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.
 +
 +
 +<code cpp>
 +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);
 +}
 +</code>
 +Alle Zahlen außer Null lassen sich mit dem entgegengesetzten Vorzeichen versehen.
 +
 +<code cpp>
 +void neg(Daten*& p)
 +{
 +  if (p != null())
 +  {  
 +    p->negativ = !p->negativ;
 +  }
 +}
 +</code>
 +
 +
 +
 +==== Strichrechnung ====
 +Der [[anwenden:rechnen#Addieren|Algorithmus zum Addieren]] 
 +und der [[anwenden:rechnen#Subtrahieren|Algorithmus zum Subtrahieren]]
 +werden in einer Funktion zusammengefasst.
 +Die Vorzeichen regeln, welche der beiden Operationen auszuführen ist.
 +
 +<code cpp>
 +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);  
 +}
 +
 +</code>
 +==== Punktrechnung ====
 +Der [[anwenden:rechnen#Multiplizieren|Algorithmus]]
 +zum Malnehmen ist bestechend einfach.
 +
 +
 +<code cpp>
 +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);
 +}
 +
 +</code>
 +[[anwenden:rechnen#Dividieren|Teilen durch eine Ziffer]] 
 +
 +<code cpp>
 +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);    
 +}
 +</code>
 +und 
 +[[anwenden:rechnen#Multiplizieren|Malnehmen mit einer Ziffer]]
 +
 +<code cpp>
 +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);    
 +}
 +</code>
 +sind Hilfsprozeduren für das mehrstellige Teilen,
 +dessen
 +[[anwenden:rechnen#Dividieren|Algorithmus]]
 +jetzt implementiert wird.
 +
 +<code cpp>
 +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
 +
 +</code>
 +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...
 +
 +<code cpp>
 +#define D(p)      (reinterpret_cast<Daten*&> (p))
 +#define ConstD(p) (reinterpret_cast<Daten* const> (p))
 +
 +</code>
 +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.
 +
 +<code cpp>
 +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;
 +}
 +
 +</code>
 +==== 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
 +>>  n *= Basis
 +>>  n += Ziffer 
 +
 +Ziffern aus einer Zahl (von hinten nach vorn)
 +
 +
 +>  geg: n >= 0
 +>  i = 0
 +>  Wiederhole
 +>>  Ziffer[i] = n % Basis
 +>>  n /= Basis
 +>  solange 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.
 +
 +<code cpp>
 +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;
 +}
 +
 +</code>
 +==== Operatoren ====
 +Die Operatoren sind weiter nichts als Umhüllungen ("Wrapper") für die oben definierten Hilfsprozeduren.
 +
 +
 +<code cpp>
 +// 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;
 +}
 +
 +</code>
 +
 +
 +
 +===== 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<(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;
 +}
 +
 +</code>
 +Alle implementierten Funktionen sind zu 
 +[[anwenden:ganzzahl_test|testen]].
  
anwenden/ganzzahl_cpp.txt · Zuletzt geändert: 2020-07-26 17:15 von 127.0.0.1

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki