Dies ist zugleich eine Gelegenheit für dich, durch ein eklatantes Scheitern die Tugend der Bescheidenheit zu lernen, welche - in deinem jungen Alter vielleicht verzeihlicherweise noch kaum entwickelt ist - eine unabdingbare Voraussetzung für dein späteres Fortkommen als Mitglied deiner Zunft und deines Standes, als Ehemann, als Untertan, als Mensch und als ein guter Christ sein wird.

— Patrick Süskind: Das Parfüm

Dies ist ein Demo- und Testprogramm für Ganzzahlimplementierungen.

//: ganzzahl_test.cpp : Tests Ganzzahlbibliothek - R.Richter 2004-10-21
///////////////////////////////////////////////////////////////////////
 
#include <iostream>
#include "ganzzahl.h"
using namespace std;
 
const long BASIS = 1L << 16;

Die ersten Tests erfordern keine Eingabefunktionen. Hier geht es um Prüfungen, ob die Grundoperationen mathematisch richtig implementiert sind. Insbesondere die 3. binomische Formel ist ein hilfsreiches Instrument.

void test_arithmetik()
{
  Ganzzahl zero, one;
  ++one;
  cout << "Natuerliche Zahlen" << endl;  
  cout << "Null == " << zero << endl;
  cout << "Eins == " << one  << endl;
 
  Ganzzahl n;
  unsigned i;
  for (i=0; i<BASIS; ++i)
  {
    ++n;  
  }     
 
  Ganzzahl base = n;
  cout << BASIS-1 << " == " << (n-one) << endl;
  cout <<   BASIS << " == " << n << endl;
  cout << 2*BASIS << " == " << (n+n) << endl;
  cout << 3*BASIS << " == " << (n+n+n) << endl;
 
  for (i=1; i<BASIS; ++i)
  {
    n += base;  
  }     
  cout << BASIS << "^2-1 == " << (n-one) << endl;    
  cout << BASIS << "^2 == " << n << endl;    
  cout << BASIS << "^4 == " << n * n << endl;    
 
  cout << "Division:\n";
  cout << BASIS << "^2/2 == " << n/(one+one) << endl;    
  // (n-1)(n+1) == n^2 - 1
  cout << BASIS << "^2/" << (BASIS-1) << " == " << n/(base-one) << endl;    
  cout << BASIS << "^2/" << (BASIS+1) << " == " << n/(base+one) << endl;
 
  cout << BASIS << "^4/2 == " << n*n/(one+one) << endl;    
  // (n-1)(n^3+n^2+n+1) = n^4 - 1
  cout << BASIS << "^4/" << (BASIS-1) << " == " << n*n/(base-one) << endl;    
  cout << BASIS << "^4/" << (BASIS+1) << " == " << n*n/(base+one) << endl;
}

Konversionen aus Ganzzahlen und Zeichenketten und umgekehrt müssen korrekt sein.

void test_konversion()
{
  cout << "Konversion aus int / std::string" << endl;
  int izahl = 1 << 31;
  Ganzzahl zahl_aus_int = izahl;
  cout << izahl << " == " << zahl_aus_int;
  cout << " == " << zahl_aus_int.to_long() << endl;
 
  std::string s = "-123456";
  Ganzzahl zahl_aus_string = s;
  cout << s << " == " << zahl_aus_string;
  cout << " == " << zahl_aus_string.to_long() << endl;
 
}

Bei logischen Tests muss statt n leider ein "double bang" !!n geschrieben werden. Automatische Rückkonvertierungen in Grundtypen int, bool oder void* würden an anderen Stellen zu Mehrdeutigkeiten führen. Deshalb wurden diese nicht implementiert. Wegen besserer Lesbarkeit ist ohnehin n==0 vorzuziehen.

void test_vergleich()
{
  Ganzzahl m("123"), n;
 
  if (!m || !!n)
  {
    throw std::string("Fehler bei Konversion / Nulltest");    
  }    
  if (n != std::string("0"))
  {
    throw std::string("Fehler bei Vergleich / Standardkonstruktor");    
  }
  if (m != 123)
  {
    throw std::string("Fehler bei Vergleich / Konversion aus int / string");    
  }    
}

Hier können Benutzereingaben getestet werden.

void test_eingabe_grundrechenarten()
{
  cout << "Eingabe zweier langer Ganzzahlen:" << endl;
  Ganzzahl eingabe1, eingabe2;
  cin >> eingabe1 >> eingabe2;
  cout << "Eingelesen:" << endl;
  cout << eingabe1 << endl << eingabe2 << endl;
  cout << "+ : " << eingabe1 + eingabe2 << endl;
  cout << "- : " << eingabe1 - eingabe2 << endl;
  cout << "* : " << eingabe1 * eingabe2 << endl;
  cout << "/ : " << eingabe1 / eingabe2 << endl;
  cout << "% : " << eingabe1 % eingabe2 << endl;
}

Ein zentraler, wichtiger Test ist die Überprüfung der Divisionsoperation. Da der Algorithmus alles andere als trivial ist, muss er besonders intensiv getestet werden. Mit zufällig gewählten Operanden wird die Division mit Probe durchgeführt.

#include <cstdio>  // sprintf()
#include <ctime>   // time()
using namespace std;
 
string zufall()
{
  char buf[20];
  int x = rand();
  if (RAND_MAX < 100000) // schlechter Zufallsgenerator  
  {
    x *= rand();
  }
  sprintf(buf, "%d", x);
  return buf;
}
 
void test_dividieren(int anzahl)
{
  int seed(time(NULL));
  srand(seed);
  cout << "Divisionstest\n"
          "Startwert Zufallsgenerator =" << seed << endl; 
  cout << "maximale Zufallszahl = " << RAND_MAX << endl;
 
  for (int i=0; i<anzahl; ++i)
  {  
    string a_strg = zufall();
    if (a_strg != "0")
    {
      a_strg += zufall() + zufall() + zufall(); // bis zu 40 Stellen
    }    
    string b_strg = zufall(); 
    while (b_strg == "0")
    {
      b_strg = zufall();   
    }
    b_strg += zufall(); // bis zu 20 Stellen   
 
    Ganzzahl a = a_strg;
    Ganzzahl b = b_strg; 
    Ganzzahl q = a / b;
    Ganzzahl r = a % b;
//    cout << a << "/" << b << "=" << q << endl;                
//    cout << a << "%" << b << "=" << r << endl;   
    Ganzzahl probe = q * b + r;
//    cout << "Probe: " << a << " == " << probe << " ? ";
    if (a != probe)
    {
      cout << a << "/" << b << "=" << q << endl;                
      cout << a << "%" << b << "=" << r << endl;   
      cout << "Probe: " << a << " == " << probe << " ? ";
      throw std::string( "Fehler bei Division! Programmabbruch." );
    }
  }    
  cout << anzahl << " Tests bestanden." << endl; 
  cout << time(0) - seed << " Sekunden." << endl;
}

Hier nun der Testtreiber.

int main()
{
  try
  {
    test_arithmetik();
    test_konversion();
    test_vergleich();
    test_eingabe_grundrechenarten();
    test_dividieren(1000000);
  }
  catch(std::string s)
  {
    cerr << s << endl;
  }
  catch(Ganzzahl::Nulldivision)
  {
    cerr << "Nulldivision" << endl;   
  }    
  catch(Ganzzahl::Bereichsfehler)
  {
    cerr << "Bereichsfehler" << endl;   
  }    
  catch(...)
  {  
    cerr << "Fehler sind aufgetreten" << endl;
  }
  cout << "Weiter mit Enter..." << flush;  
  cin.sync();
  cin.get();  
  return 0;   
}

Getestet wurden mehrere Versionen,

• eine einfache mit dezimalen Zeichenketten und
• zwei referenzzählende Implementierungen zur Basis 65536,
  • eine mit einem Vektor aus Ziffern und
  • eine mit eigener Speicherverwaltung.

Drei Compiler,

• MS Visual C++ 6,
• der in Dev C++ enthaltene Minimal GNU for Windows (mingw) sowie
• Linux g++ 3.3.2,

kamen in zwei Konfigurationen (nichtoptimiert / Debug, optimiert / Release) zum Einsatz.

Für 1 Million Divisionen mit Probe für Zahlen der Größenordnung ca. 10^36 / 10^18 benötigten die Implementierungen folgende Zeiten (in Sekunden) auf einem Pentium M System 1.5 GHz:

Eindeutiger Gewinner ist die Implementierung mit eigener Speicherverwaltung. Hier sind die Quelltexte:

• ganzzahl.h
• ganzzahl.cpp
• ganzzahl_test.cpp