Unterabschnitte


A.2.1 Größter gemeinsamer Teiler

Die Musterlösung erfüllt die Aufgabenstellung für C++ vollständig in einem Programm, welches mit Präprozessordirektiven wahlweise so kompiliert werden kann, daß die Laufzeit gemessen wird (durch Aktivieren der Zeile
#define MODUS MESSE_LAUFZEIT
im Quelltext oder durch Aufruf des Compilers mit der Option -DMODUS=1), oder so daß die Anzahl der Anweisungen mitprotokolliert wird (mit der Zeile
#define MODUS ZAEHLE_ANWEISUNGEN
beziehungsweise -DMODUS=2).

Weiterhin werden in der C++-Version bei der Laufzeitmessung nicht nur die für die Gruppen A, B, und C geforderten Kombinationen von $m$ und $n$ getestet, sondern noch mehr dazwischenliegende; und die so ermittelten Laufzeiten werden (getrennt nach Euklid und dem einfachen Algorithmus) in einer Datei hinterlegt. Aus diesen Dateien wurde dann mit gnuplot das Bild A.2 generiert.

Die Java-Version ist dagegen nur so gebaut, daß die Laufzeit bestimmt wird. Die Vorgehensweise ebenso wie ausgegebene Anzahl der Anweisungen würde der C++-Version entsprechen; deshalb habe ich mir die Mühe erspart.

Der erste Aufgabenteil (Umsetzen des Algorithmus) ist jeweils implizit enthalten.

A.2.1.1 Java-Version

// Time-stamp: "(24.03.02 21:04) Euklid.java [Klaus@Wachtler.de]"
//
// Kleines Javaprogramm zur Demonstration des Euklidschen Algorithmus
// im Vergleich zu einem einfachen Algorithmus (stumpfisttrumpf()).

import java.util.*;

class Euklid
{

    //
    //       Euklidscher Algorithmus:
    //       +---------------------------------------+
    //       |                                       |
    //       | +-------------------------------------+
    //       | | r = m mod n                         |
    //       | +-------------------------------------+
    //       | |               r = 0 ?               |
    //       | |                  |                  |
    //       | |----- ja ---------+---- nein --------+
    //       | |                  |                  |
    //       | | Ergebnis = n     | m = n            |
    //       | +------------------+------------------+
    //       | | <--Euklidsch. A. | n = r            |
    //       | +------------------+------------------+
    //       |                                       |
    //       +---------------------------------------+
    //

    static int euklid( int m, int n )
    {
        int r;


        while( true )
        {
            r = m % n;

            if( r==0)
            {
                return n;
            }
            else
            {
                m = n;
                n = r;
            }
        }

    } // int euclid( int m, int n )


    //
    //       stumpfisttrumpf:
    //       +------------------------------------+
    //       |               m>n                  |
    //       |                |                   |
    //       +--- ja  --------+--- nein ----------+
    //       | Vertausche m,n |                   |
    //       +------------------------------------+
    //       |  für i = m ... 1  (-1)             |
    //       |   +--------------------------------+
    //       |   |  m/i ohne Rest teilbar         |
    //       |   |      UND                       |
    //       |   |  n/i ohne Rest teilbar         |
    //       |   |          |                     |
    //       |   +-- nein --+-- ja ---------------+
    //       |   |          |                     |
    //       |   |          | ggT = i             |
    //       |   |          +---------------------+
    //       |   |          | <- stumpfisttrumpf  |
    //       +---+----------+---------------------+
    //
    //

    static int stumpfisttrumpf( int m, int n )
    {
        if( m>n )
        {
            int tmp = m;
            m = n;
            n = tmp;
        }

        for( int i=m; m>=1; i-- )
        {
            if( ( m % i ) == 0 )
            {
                if( ( n % i ) == 0 )
                {
                    return i;
                }
            }
        }

        return 0; // eigentlich egal, aber vermeidet Compilerwarnungen

    } // int stumpfisttrumpf( int m, int n )


    public static void kombiniere_m_n_euklid( int mvon, int mbis,
                                              int nvon, int nbis,
                                              int NTIME
                                              )
    {
        long start = System.currentTimeMillis();
        for( int i=0; i<NTIME; i++ )
        {
            for( int m=mvon; m<=mbis; m++ )
            {
                for( int n=nvon; n<=nbis; n++ )
                {
                    int erg = euklid( m, n );
                }
            }
        }
        long ende = System.currentTimeMillis();
        System.out.println( "euklid: m = "
                            + mvon
                            + ".."
                            + mbis
                            + "; n = "
                            + nvon
                            + ".."
                            + nbis
                            + "  Zeit = "
                            + ( (double)( ende - start )
                                /NTIME
                                /( (nbis-nvon+1)*(mbis-mvon+1) )
                                )
                            + " msec"
                            );
    }

    public static void kombiniere_m_n_stumpf( int mvon, int mbis,
                                              int nvon, int nbis,
                                              int NTIME
                                              )
    {
        long start = System.currentTimeMillis();
        for( int i=0; i<NTIME; i++ )
        {
            for( int m=mvon; m<=mbis; m++ )
            {
                for( int n=nvon; n<=nbis; n++ )
                {
                    int erg = stumpfisttrumpf( m, n );
                }
            }
        }
        long ende = System.currentTimeMillis();
        System.out.println( "stumpf: m = "
                            + mvon
                            + ".."
                            + mbis
                            + "; n = "
                            + nvon
                            + ".."
                            + nbis
                            + "  Zeit = "
                            + ( (double)( ende - start )
                                /NTIME
                                /( (nbis-nvon+1)*(mbis-mvon+1) )
                                )
                            + " msec"
                            );
    }
    public static void main( String args[] )
    {
        kombiniere_m_n_euklid( 1, 20, 1, 20, 1000 );
        kombiniere_m_n_euklid( 1001, 1020, 1001, 1020, 1000 );
        kombiniere_m_n_euklid( 1000001, 1000020, 1000001, 1000020, 1000 );

        kombiniere_m_n_stumpf( 1, 20, 1, 20, 10 );
        kombiniere_m_n_stumpf( 1001, 1020, 1001, 1020, 1 );
        kombiniere_m_n_stumpf( 1000001, 1000020, 1000001, 1000020, 1 );
    }


} // class Euklid

Ausgabe der Laufzeiten:

euklid: m = 1..20; n = 1..20  Zeit = 1.575E-4 msec
euklid: m = 1001..1020; n = 1001..1020  Zeit = 1.7E-4 msec
euklid: m = 1000001..1000020; n = 1000001..1000020  Zeit = 1.7250000000000002E-4 msec
stumpf: m = 1..20; n = 1..20  Zeit = 0.0010 msec
stumpf: m = 1001..1020; n = 1001..1020  Zeit = 0.035 msec
stumpf: m = 1000001..1000020; n = 1000001..1000020  Zeit = 34.0925 msec


A.2.1.2 C++-Version

// Time-stamp: "16.03.04 16:46 euklid.cpp klaus@wachtler.de"
//
// Euklidscher Algorithmus oder einfache Bestimmung des ggT;
// wahlweise mit Messung der Laufzeiten
// oder Anzahl der verschiedenen Operationen
//
// ANSI-C++
//
// Linux:    g++ -Wall euklid.cpp && a.out
//
// VC++ 6.0: cl /Zi /GX auklid.cpp
//           .\euklid


#define MESSE_NIX            0
#define MESSE_LAUFZEIT       1
#define ZAEHLE_ANWEISUNGEN   2


// Es kann wahlweise die Laufzeit bestimmt werden,
// oder die Anzahlen bestimmter Anweisungen gezählt werden.
// Dazu entweder vor dem Kompilieren die entsprechende der drei
// folgenden #define-Anweisungen auskommentieren, oder den Compiler
// mit einer der Optionen -DMODUS=1 (für Laufzeit) oder -DMODUS=2
// (für Anzahl Anweisungen) aufrufen:
//#define MODUS  MESSE_NIX
//#define MODUS  MESSE_LAUFZEIT
//#define MODUS  ZAEHLE_ANWEISUNGEN

#include <cstdio>


// Die Laufzeit wird mit clock() gemessen
#if MODUS == MESSE_LAUFZEIT
#include <ctime>
#endif // if MODUS==MESSE_LAUFZEIT



// Es werden
// - Zuweisungen
// - Additionen/Subtraktionen
// - Mulitiplikationen
// - Divisionen/Modulo
// - Vertauschungen
// - Vergleiche
// gezählt:
#if MODUS == ZAEHLE_ANWEISUNGEN
int AnzZuw;
int AnzAddSub;
int AnzMul;
int AnzDivMod;
int AnzSwap;
int AnzCmp;
#endif // if MODUS==ZAEHLE_ANWEISUNGEN


//
//       Euklidscher Algorithmus:
//       +---------------------------------------+
//       |                                       |
//       | +-------------------------------------+
//       | | r = m mod n                         |
//       | +-------------------------------------+
//       | |               r = 0 ?               |
//       | |                  |                  |
//       | |----- ja ---------+---- nein --------+
//       | |                  |                  |
//       | | Ergebnis = n     | m = n            |
//       | +------------------+------------------+
//       | | <--Euklidsch. A. | n = r            |
//       | +------------------+------------------+
//       |                                       |
//       +---------------------------------------+
//


int euclid( int m, int n )
{
  int r;


  while( 1 )
    {
#if MODUS == ZAEHLE_ANWEISUNGEN
      AnzDivMod++;
#endif // if MODUS==ZAEHLE_ANWEISUNGEN
      r = m % n;

#if MODUS == ZAEHLE_ANWEISUNGEN
      AnzCmp++;
#endif // if MODUS==ZAEHLE_ANWEISUNGEN
      if( r==0)
        {
          return n;
        }
      else
        {
#if MODUS == ZAEHLE_ANWEISUNGEN
      AnzZuw++;
#endif // if MODUS==ZAEHLE_ANWEISUNGEN
          m = n;
#if MODUS == ZAEHLE_ANWEISUNGEN
      AnzZuw++;
#endif // if MODUS==ZAEHLE_ANWEISUNGEN
          n = r;
        }
    }

  return 0; // eigentlich egal, aber vermeidet Compilerwarnungen

} // int euclid( int m, int n )


//
//       stumpfisttrumpf:
//       +------------------------------------+
//       |               m>n                  |
//       |                |                   |
//       +--- ja  --------+--- nein ----------+
//       | Vertausche m,n |                   |
//       +------------------------------------+
//       |  für i = m ... 1  (-1)             |
//       |   +--------------------------------+
//       |   |  m/i ohne Rest teilbar         |
//       |   |      UND                       |
//       |   |  n/i ohne Rest teilbar         |
//       |   |          |                     |
//       |   +-- nein --+-- ja ---------------+
//       |   |          |                     |
//       |   |          | ggT = i             |
//       |   |          +---------------------+
//       |   |          | <- stumpfisttrumpf  |
//       +---+----------+---------------------+
//
//

int stumpfisttrumpf( int m, int n )
{
#if MODUS == ZAEHLE_ANWEISUNGEN
  AnzCmp++;
#endif // if MODUS==ZAEHLE_ANWEISUNGEN
  if( m>n )
    {
#if MODUS == ZAEHLE_ANWEISUNGEN
      AnzSwap++;
#endif // if MODUS==ZAEHLE_ANWEISUNGEN
      int tmp = m;
      m = n;
      n = tmp;
    }
  for( int i=m; m>=1; i-- )
    {
#if MODUS == ZAEHLE_ANWEISUNGEN
      AnzDivMod++;
      AnzCmp++;
#endif // if MODUS==ZAEHLE_ANWEISUNGEN
      if( ( m % i ) == 0 )
        {
#if MODUS == ZAEHLE_ANWEISUNGEN
          AnzDivMod++;
          AnzCmp++;
#endif // if MODUS==ZAEHLE_ANWEISUNGEN
          if( ( n % i ) == 0 )
            {
              return i;
            }
        }
    }

  return 0; // eigentlich egal, aber vermeidet Compilerwarnungen

} // int stumpfisttrumpf( int m, int n )

//void kombiniere_m_n( ggt_t ggt,
void kombiniere_m_n( int (*ggt)( int m, int n ),
                     int mvon,
                     int mbis,
                     int nvon,
                     int nbis,
                     int NTIME
#if MODUS == MESSE_LAUFZEIT
                     , FILE *f     // Ausgabe der Laufzeiten
#endif // if MODUS==MESSE_LAUFZEIT
                     )
{

#if MODUS == ZAEHLE_ANWEISUNGEN
  AnzZuw = 0;
  AnzAddSub = 0;
  AnzMul = 0;
  AnzDivMod = 0;
  AnzSwap = 0;
  AnzCmp = 0;
#endif // if MODUS==ZAEHLE_ANWEISUNGEN



#if MODUS == MESSE_LAUFZEIT
  clock_t anf, end;

  anf = clock();

  for( int i=0; i<NTIME; i++ )
    {
#endif // if MODUS==MESSE_LAUFZEIT



      for( int m=mvon; m<=mbis; m++ )
        {
          for( int n=nvon; n<=nbis; n++ )
            {

              /*int erg =*/ ggt( m, n );

            }
        }


#if MODUS == MESSE_LAUFZEIT
    }

  end = clock();
  printf( "Laufzeit m,n=[%8d,%8d],[%8d,%8d]: %g msec/ggT\n",
          mvon, mbis,
          nvon, nbis,
          ( (double)( end - anf )
            /CLOCKS_PER_SEC
            /NTIME
            /( (nbis-nvon+1)*(mbis-mvon+1) ) // Anzahl ggT
            *1000    // Umrechnung von sec auf msec
            )
          );
  fprintf( f,
           "%10d %g\n",
           mvon,
           ( (double)( end - anf )
             /CLOCKS_PER_SEC
             /NTIME
             /( (nbis-nvon+1)*(mbis-mvon+1) ) // Anzahl ggT
             *1000    // Umrechnung von sec auf msec
             )
           );
#endif // if MODUS==MESSE_LAUFZEIT


// Es werden
// - Zuweisungen
// - Additionen/Subtraktionen
// - Multiplikationen
// - Divisionen/Modulo
// - Vertauschungen
// gezählt:
#if MODUS == ZAEHLE_ANWEISUNGEN
  printf( "Anzahl Anweisungen für m,n=[%8d,%8d],[%8d,%8d]:\n",
          mvon, mbis,
          nvon, nbis
          );
  printf( "AnzZuw    = %9.2f\n",
          (double)AnzZuw/( (nbis-nvon+1)*(mbis-mvon+1) )
          );
  printf( "AnzAddSub = %9.2f\n",
          (double)AnzAddSub/( (nbis-nvon+1)*(mbis-mvon+1) )
          );
  printf( "AnzMul    = %9.2f\n",
          (double)AnzMul/( (nbis-nvon+1)*(mbis-mvon+1) )
          );
  printf( "AnzDivMod = %9.2f\n",
          (double)AnzDivMod/( (nbis-nvon+1)*(mbis-mvon+1) )
          );
  printf( "AnzSwap   = %9.2f\n",
          (double)AnzSwap/( (nbis-nvon+1)*(mbis-mvon+1) )
          );
  printf( "AnzCmp    = %9.2f\n",
          (double)AnzCmp/( (nbis-nvon+1)*(mbis-mvon+1) )
          );
  printf( "\n" );
#endif // if MODUS==ZAEHLE_ANWEISUNGEN

}


int main( int nargs, char **args )
{
#if MODUS == MESSE_LAUFZEIT
  FILE *f_euklid = fopen( "laufzeit_ggt_euklid_delta_ueber_n.xy", "w" );
  FILE *f_einfach = fopen( "laufzeit_ggt_einfach_delta_ueber_n.xy", "w" );
  if( !f_euklid || !f_einfach )
  {
    fprintf( stderr, "kann Dateien nicht öffnen!\n" );
    return 1;
  }
#endif // if MODUS==MESSE_LAUFZEIT

  printf( "\nVersion Euklid\n" );
  kombiniere_m_n( euclid,
                  1, 20, 1, 20,
                  100000
#if MODUS == MESSE_LAUFZEIT
                  , f_euklid
#endif // if MODUS==MESSE_LAUFZEIT
                  );
  kombiniere_m_n( euclid,
                  1001, 1020, 1001, 1020,
                  100000
#if MODUS == MESSE_LAUFZEIT
                  , f_euklid
#endif // if MODUS==MESSE_LAUFZEIT
                  );
#if MODUS == MESSE_LAUFZEIT
  kombiniere_m_n( euclid,
                  5001, 5020, 5001, 5020,
                  100000
#if MODUS == MESSE_LAUFZEIT
                  , f_euklid
#endif // if MODUS==MESSE_LAUFZEIT
                  );
  kombiniere_m_n( euclid,
                  10001, 10020, 10001, 10020,
                  100000
#if MODUS == MESSE_LAUFZEIT
                  , f_euklid
#endif // if MODUS==MESSE_LAUFZEIT
                  );
  kombiniere_m_n( euclid,
                  50001, 50020, 50001, 50020,
                  100000
#if MODUS == MESSE_LAUFZEIT
                  , f_euklid
#endif // if MODUS==MESSE_LAUFZEIT
                  );
  kombiniere_m_n( euclid,
                  100001, 100020, 100001, 100020,
                  100000
#if MODUS == MESSE_LAUFZEIT
                  , f_euklid
#endif // if MODUS==MESSE_LAUFZEIT
                  );
  kombiniere_m_n( euclid,
                  500001, 500020, 500001, 500020,
                  100000
#if MODUS == MESSE_LAUFZEIT
                  , f_euklid
#endif // if MODUS==MESSE_LAUFZEIT
                  );
#endif // if MODUS==MESSE_LAUFZEIT
  kombiniere_m_n( euclid,
                  1000001, 1000020, 1000001, 1000020,
                  100000
#if MODUS == MESSE_LAUFZEIT
                  , f_euklid
#endif // if MODUS==MESSE_LAUFZEIT
                  );
  printf( "\nVersion einfacher Algorithmus\n" );
  kombiniere_m_n( stumpfisttrumpf,
                  1, 20, 1, 20,
                  5000
#if MODUS == MESSE_LAUFZEIT
                  , f_einfach
#endif // if MODUS==MESSE_LAUFZEIT
                  );
  kombiniere_m_n( stumpfisttrumpf,
                  1001, 1020, 1001, 1020,
                  500
#if MODUS == MESSE_LAUFZEIT
                  , f_einfach
#endif // if MODUS==MESSE_LAUFZEIT
                  );
#if MODUS == MESSE_LAUFZEIT
  kombiniere_m_n( stumpfisttrumpf,
                  5001, 5020, 5001, 5020,
                  100
#if MODUS == MESSE_LAUFZEIT
                  , f_einfach
#endif // if MODUS==MESSE_LAUFZEIT
                  );
  kombiniere_m_n( stumpfisttrumpf,
                  10001, 10020, 10001, 10020,
                  10
#if MODUS == MESSE_LAUFZEIT
                  , f_einfach
#endif // if MODUS==MESSE_LAUFZEIT
                  );
  kombiniere_m_n( stumpfisttrumpf,
                  50001, 50020, 50001, 50020,
                  1
#if MODUS == MESSE_LAUFZEIT
                  , f_einfach
#endif // if MODUS==MESSE_LAUFZEIT
                  );
  kombiniere_m_n( stumpfisttrumpf,
                  100001, 100020, 100001, 100020,
                  1
#if MODUS == MESSE_LAUFZEIT
                  , f_einfach
#endif // if MODUS==MESSE_LAUFZEIT
                  );
  kombiniere_m_n( stumpfisttrumpf,
                  500001, 500020, 500001, 500020,
                  1
#if MODUS == MESSE_LAUFZEIT
                  , f_einfach
#endif // if MODUS==MESSE_LAUFZEIT
                  );
#endif // if MODUS==MESSE_LAUFZEIT
  kombiniere_m_n( stumpfisttrumpf,
                  1000001, 1000020, 1000001, 1000020,
                  1
#if MODUS == MESSE_LAUFZEIT
                  , f_einfach
#endif // if MODUS==MESSE_LAUFZEIT
                  );



  return 0;
} // main( int nargs, char **args )

Ausgabe der Laufzeiten:

Version Euklid
Laufzeit m,n=[       1,      20],[       1,      20]: 0.00014575 msec/ggT
Laufzeit m,n=[    1001,    1020],[    1001,    1020]: 0.000217 msec/ggT
Laufzeit m,n=[    5001,    5020],[    5001,    5020]: 0.000218 msec/ggT
Laufzeit m,n=[   10001,   10020],[   10001,   10020]: 0.000223 msec/ggT
Laufzeit m,n=[   50001,   50020],[   50001,   50020]: 0.00022025 msec/ggT
Laufzeit m,n=[  100001,  100020],[  100001,  100020]: 0.00021725 msec/ggT
Laufzeit m,n=[  500001,  500020],[  500001,  500020]: 0.0002185 msec/ggT
Laufzeit m,n=[ 1000001, 1000020],[ 1000001, 1000020]: 0.00022575 msec/ggT

Version einfacher Algorithmus
Laufzeit m,n=[       1,      20],[       1,      20]: 0.000305 msec/ggT
Laufzeit m,n=[    1001,    1020],[    1001,    1020]: 0.02595 msec/ggT
Laufzeit m,n=[    5001,    5020],[    5001,    5020]: 0.12775 msec/ggT
Laufzeit m,n=[   10001,   10020],[   10001,   10020]: 0.2525 msec/ggT
Laufzeit m,n=[   50001,   50020],[   50001,   50020]: 1.3 msec/ggT
Laufzeit m,n=[  100001,  100020],[  100001,  100020]: 2.525 msec/ggT
Laufzeit m,n=[  500001,  500020],[  500001,  500020]: 12.65 msec/ggT
Laufzeit m,n=[ 1000001, 1000020],[ 1000001, 1000020]: 25.3 msec/ggT

Ausgabe der Anzahlen der Anweisungen, nach Gruppen getrennt:

Version Euklid
Anzahl Anweisungen für m,n=[       1,      20],[       1,      20]:
AnzZuw    =      3.49
AnzAddSub =      0.00
AnzMul    =      0.00
AnzDivMod =      2.75
AnzSwap   =      0.00
AnzCmp    =      2.75

Anzahl Anweisungen für m,n=[    1001,    1020],[    1001,    1020]:
AnzZuw    =      5.54
AnzAddSub =      0.00
AnzMul    =      0.00
AnzDivMod =      3.77
AnzSwap   =      0.00
AnzCmp    =      3.77

Anzahl Anweisungen für m,n=[ 1000001, 1000020],[ 1000001, 1000020]:
AnzZuw    =      5.65
AnzAddSub =      0.00
AnzMul    =      0.00
AnzDivMod =      3.83
AnzSwap   =      0.00
AnzCmp    =      3.83


Version einfacher Algorithmus
Anzahl Anweisungen für m,n=[       1,      20],[       1,      20]:
AnzZuw    =      0.00
AnzAddSub =      0.00
AnzMul    =      0.00
AnzDivMod =      8.24
AnzSwap   =      0.47
AnzCmp    =      9.24

Anzahl Anweisungen für m,n=[    1001,    1020],[    1001,    1020]:
AnzZuw    =      0.00
AnzAddSub =      0.00
AnzMul    =      0.00
AnzDivMod =    962.33
AnzSwap   =      0.47
AnzCmp    =    963.33

Anzahl Anweisungen für m,n=[ 1000001, 1000020],[ 1000001, 1000020]:
AnzZuw    =      0.00
AnzAddSub =      0.00
AnzMul    =      0.00
AnzDivMod = 950018.44
AnzSwap   =      0.47
AnzCmp    = 950019.44

A.2.1.3 Kommentar zu den Ergebnissen

Aus den Ergebnissen kann man leicht folgende grundlegenden Erkenntnisse ziehen, die bei vielen Aufgabenstellungen immer wiederkehren:

www.wachtler.de