namespace cpp {}

C++ lernen, kennen, anwenden

Benutzer-Werkzeuge

Webseiten-Werkzeuge


anwenden:ganzzahl_cpp

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);
}

Teilen durch eine Ziffer

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 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.

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.

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