namespace cpp {}

C++ lernen, kennen, anwenden

Benutzer-Werkzeuge

Webseiten-Werkzeuge


Action disabled: source
anwenden:ganzzahl

Ganzzahl : ein Datentyp für beinahe beliebig große Ganzzahlen

Gott schuf die ganzen Zahlen. Der Rest ist Menschenwerk.
— Leopold Kronecker

Die Grunddatentypen haben einen beschränkten Wertebereich. Dieser ist für manche Anwendung zu klein. Verschlüsselungsalgorithmen z.B. arbeiten heute mit 512 Bit, d.h. also etwa 150 Dezimalstellen. Dafür wird ein Ganzzahltyp benötigt, der Werte mit beliebig vielen Stellen erlaubt, zumindest soweit der Hauptspeicher des Rechners reicht.

Eine Vielzahl von Bibliotheken (z.B. GMP = GNU Multiprecision library, BigNum, MPInt, Mint, bigInt, LiDIA, bnlib, CLN) widmet sich der Fragestellung großer Ganzzahlen für bestimmte Compiler und Plattformen. Unter der Bezeichnung N 4029 gibt es einen Standardisierungsvorschlag auf der Basis von Boost.Integer.

Anforderungen

Was muss ein solcher Ganzzahltyp beherrschen? Natürlich Rechnen (+ - * / und Divisionsrest % als "fünfte" Rechenart), Erhöhen und Vermindern, Vergleiche. Die Ein- und Ausgabe erfolgt über Datenströme der iostream-Bibliothek. Die Umwandlung von und zu Zeichenketten (string) und aus int muss möglich sein. Bitweise Operationen werden nicht unterstützt.

Klassenschnittstelle

//: ganzzahl.h : Ganzzahlen beliebiger Genauigkeit - R.Richter 2004-09-24
/////////////////////////////////////////////////////////////////////////
 
#ifndef GANZZAHL_H
#define GANZZAHL_H
 
// Abhängigkeiten
#include <string>
#include <iostream>
 
class Ganzzahl
{
public:

Ganzzahlen können ohne Vorgabe (0), aus einem int-Wert oder aus einer Zeichenkette wie "-1234567890" gebildet werden.

  // Konstruktoren
  Ganzzahl();
  Ganzzahl(long n);
  Ganzzahl(std::string s);

Die Rückwandlung in eine Zeichenkette ist jederzeit möglich, die Umwandlung in int jedoch nur, wenn die Grenzen des Zieldatentyps eingehalten werden.

  // Konversion
  std::string to_string() const;
  long to_long() const;

Andernfalls wird eine Ganzzahl::Bereichsfehler-Ausnahme ausgelöst. Die andere Fehlerart tritt beim Dividieren auf.

  // Fehlerklassen
  class Bereichsfehler {};
  class Nulldivision {};

Die gewöhnlichen Rechenoperationen werden weiter unten über die C-typischen Verbundoperatoren definiert.

  // Operatoren
  Ganzzahl& operator+=(Ganzzahl const& n);
  Ganzzahl& operator-=(Ganzzahl const& n);
  Ganzzahl& operator*=(Ganzzahl const& n);
  Ganzzahl& operator/=(Ganzzahl const& n);
  Ganzzahl& operator%=(Ganzzahl const& n);

Inkrement und Dekrement existieren als voran- und nachgestellte Operanden mit unterschiedlicher Bedeutung.

  Ganzzahl& operator++();    // Prefix
  Ganzzahl& operator--();
  Ganzzahl  operator++(int); // Postfix
  Ganzzahl  operator--(int);

Das Vorzeichen - liefert die entgegengesetzte Zahl.

  Ganzzahl operator-() const;

Häufig wird in C auf "Null sein" geprüft:

  bool operator!() const;

Da die Implementierung mit Zeigern p auf dynamisch bereitgestellten Speicher zugreifen wird, sind Kopierkonstruktor, Zuweisungsoperator und Destruktor zu definieren. Die Entscheidung für char* scheint vorerst willkürlich. Alternativ wäre hier ein privater std::string denkbar. Dann wäre manches einfacher, auch die drei nachstehenden Funktionen bräuchten nicht geschrieben werden.

  // Kopie, Zuweisung, Destruktor
  Ganzzahl(Ganzzahl const& n);
  Ganzzahl& operator=(Ganzzahl const& n);
 ~Ganzzahl();
private:
  char* p; // dynamisch allokiert

Einzelnen Rechenoperationen wird der Zugriff auf die interne Datenrepräsentation gestattet, z.B. einem Vergleichsoperator.

  // Freunde
  friend bool operator<(Ganzzahl const& m, Ganzzahl const& n);
};

Damit ist die Klasse vollständig definiert. Als globale Funktionen angemeldet werden der Satz der Vergleichsoperatoren

// Vergleich
bool operator< (Ganzzahl const& m, Ganzzahl const& n);
bool operator> (Ganzzahl const& m, Ganzzahl const& n);
bool operator<=(Ganzzahl const& m, Ganzzahl const& n);
bool operator>=(Ganzzahl const& m, Ganzzahl const& n);
bool operator==(Ganzzahl const& m, Ganzzahl const& n);
bool operator!=(Ganzzahl const& m, Ganzzahl const& n);

und die zweistelligen Rechenoperationen

// symmetrische arithmetische Funktionen
Ganzzahl operator+(Ganzzahl const& m, Ganzzahl const& n);
Ganzzahl operator-(Ganzzahl const& m, Ganzzahl const& n);
Ganzzahl operator*(Ganzzahl const& m, Ganzzahl const& n);
Ganzzahl operator/(Ganzzahl const& m, Ganzzahl const& n);
Ganzzahl operator%(Ganzzahl const& m, Ganzzahl const& n);

sowie Ein- und Ausgabeoperatoren.

// I/O
std::ostream& operator<<(std::ostream& os, Ganzzahl const& n);
std::istream& operator>>(std::istream& is, Ganzzahl& n);

inline-Methoden

Für fast alle globalen Operationen sind inline-Implementierungen möglich, bei denen der Überbau eines zusätzlichen Funktionsaufrufs vermieden und die entsprechenden Anweisungen direkt eingebaut werden. Dazu werden dem Compiler diese Funktionsrümpfe offengelegt. Alle Vergleiche lassen sich auf die Kleiner-Als-Operation zurückführen. Dies ist eine kleine Übung in mathematischer Logik:

inline bool operator> (Ganzzahl const& m, Ganzzahl const& n)
{
  return n < m;
}
 
inline bool operator>=(Ganzzahl const& m, Ganzzahl const& n)
{
  return !(m < n);
}
 
inline bool operator<=(Ganzzahl const& m, Ganzzahl const& n)
{
  return !(n < m);
}
 
inline bool operator==(Ganzzahl const& m, Ganzzahl const& n)
{
  return !(m < n || n < m);
}
 
inline bool operator!=(Ganzzahl const& m, Ganzzahl const& n)
{
  return m < n || n < m;
}

Die Ausgabe erfolgt über den Umweg einer Zeichenkette.

inline std::ostream& operator<<(std::ostream& os, Ganzzahl const& n)
{
  return os << n.to_string();
}

Die zweistelligen Rechenoperationen werden auf die zugeordneten Verbundoperatoren zurückgeführt. Für m+n werden die Anweisungen

 // Ganzzahl summe = m; // Kopie des linken Operanden
 // summe += n;         
 // return summe;

ausgeführt, ohne dem Zwischenergebnis einen Namen verleihen zu müssen.

inline Ganzzahl operator+(Ganzzahl const& m, Ganzzahl const& n)
{
  return Ganzzahl(m) += n;
}
 
inline Ganzzahl operator-(Ganzzahl const& m, Ganzzahl const& n)
{
  return Ganzzahl(m) -= n;
}
 
inline Ganzzahl operator*(Ganzzahl const& m, Ganzzahl const& n)
{
  return Ganzzahl(m) *= n;
}
 
inline Ganzzahl operator/(Ganzzahl const& m, Ganzzahl const& n)
{
  return Ganzzahl(m) /= n;
}
 
inline Ganzzahl operator%(Ganzzahl const& m, Ganzzahl const& n)
{
  return Ganzzahl(m) %= n;
}

Die nachgestellten Operatoren ++ und -- heben den alten Wert auf, der nach der Wertänderung für weitere Rechenoperationen benutzt wird.

inline Ganzzahl Ganzzahl::operator++(int)
{
  Ganzzahl alt(*this);
  ++ *this;
  return alt;
}
 
inline Ganzzahl Ganzzahl::operator--(int)
{
  Ganzzahl alt(*this);
  -- *this;
  return alt;
}
 
#endif // GANZZAHL_H

Die Klassenschnittstelle und eine Reihe globaler Funktionen sind damit festgelegt. Was noch fehlt, ist der Teil, der harte Arbeit verlangt.

anwenden/ganzzahl.txt · Zuletzt geändert: 2020-07-26 17:05 von 127.0.0.1

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki