namespace cpp {}

C++ lernen, kennen, anwenden

Benutzer-Werkzeuge

Webseiten-Werkzeuge


anwenden:ganzzahl_test
no way to compare when less than two revisions

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.


anwenden:ganzzahl_test [2020-05-14 15:03] (aktuell) – angelegt - Externe Bearbeitung 127.0.0.1
Zeile 1: Zeile 1:
 +====== Ganzzahl_Test : Testprogramme für beliebig genaue Ganzzahlen ======
 +> 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.
 +
 +<code cpp>
 +//: ganzzahl_test.cpp : Tests Ganzzahlbibliothek - R.Richter 2004-10-21
 +///////////////////////////////////////////////////////////////////////
 +
 +#include <iostream>
 +#include "ganzzahl.h"
 +using namespace std;
 +
 +const long BASIS = 1L << 16;
 +
 +</code>
 +
 +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.
 +
 +<code cpp>
 +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;
 +}    
 +
 +</code>
 +
 +Konversionen aus Ganzzahlen und Zeichenketten und umgekehrt müssen korrekt sein.
 +
 +<code cpp>
 +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;
 +  
 +}
 +
 +</code>
 +
 +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.
 +
 +<code cpp>
 +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");    
 +  }    
 +}    
 +
 +</code>
 +
 +Hier können Benutzereingaben getestet werden.
 +
 +<code cpp>
 +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;
 +}
 +
 +</code>
 +
 +Ein zentraler, wichtiger Test ist die Überprüfung der Divisionsoperation.
 +Da der [[anwenden:rechnen#Dividieren|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.
 +
 +<code cpp>
 +#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;
 +}    
 +
 +</code>
 +Hier nun der Testtreiber.
 +
 +<code cpp>
 +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;   
 +}    
 +
 +</code>
 +
 +
 +
 +===== Laufzeit Ganzzahlarithmetik =====
 +Getestet wurden mehrere Versionen, 
 +
 +
 +  * eine {{arithm.cpp|einfache}} mit dezimalen Zeichenketten und
 +  * zwei referenzzählende Implementierungen zur Basis 65536,
 +    * eine mit einem Vektor aus Ziffern und 
 +    * eine mit eigener Speicherverwaltung.
 +
 +| arithm    | <string>       | Basis 10   |
 +| Ganzzahl2 | vector<Ziffer> | Basis $2^{16}$|
 +| Ganzzahl  | new / delete   | Basis $2^{16}$|
 +
 +
 +Drei Compiler, 
 +
 +
 +  * MS Visual C++ 6, 
 +  * der in [[http://www.bloodshed.net/devcpp.html|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: 
 +
 +
 +| Compiler          | arithm | Ganzzahl2 | Ganzzahl|
 +| Dev C++ not opt.  |   187  |    272    |    65|
 +| Dev C++ optimized |    94  |     77    |    48|
 +| MS VC++ 6 Debug    1496  |    863    |   213|
 +| MS VC++ 6 Release |    92  |     73    |    36|
 +| Linux g++ not opt.|   213  |    328    |    56|
 +| Linux g++ -O3        99  |     66    |    36|
 +
 +
 +Eindeutiger Gewinner ist die 
 +[[anwenden:ganzzahl_cpp|Implementierung mit eigener Speicherverwaltung]].
 +Hier sind die Quelltexte:
 +
 +
 +  * {{ganzzahl.h}}
 +  * {{ganzzahl.cpp}}
 +  * {{ganzzahl_test.cpp}}
  
anwenden/ganzzahl_test.txt · Zuletzt geändert: 2020-05-14 15:03 von 127.0.0.1

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki