Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2016 / Algorithmen und Datenstrukturen / Material / Java Vorlage H2-2


Inhaltsbereich

Java Vorlage H2-2

Java Gerüst zur Bearbeitung der Hausaufgabe H2-2 "Multiplikation großer ganzer Zahlen II". Die Vorlage bringt bereits einen Benchmark und viele nützliche Helfer mit. Die Vorlage kompiliert, aber die Methoden mal_langsam und mal_schneller müssen noch verändert werden, damit die Kontrollausgabe am Anfang nicht mehr "falsch" meldet.

Java source code icon Ganzzahl.java — Java source code, 9 KB (9217 bytes)

Dateiinhalt

import java.util.Arrays;
import java.util.Random;

/* Bibliothek fuer positive ganze Zahlen.
 */

public class Ganzzahl {
  
  // Alle Zahlen im gleichen Stellenwertsystem. 10 fuer gut menschenlesbare
  // Anzeige
  final static int stellenwert=10;

  // Hier wird die Zahl gespeichert
  int[] werte;

  /* Erzeuge eine Ganzzahl mit nur einer Stelle
   */
  public Ganzzahl(int stelle) {
  werte = new int[1];
  werte[0] = stelle;
  }

  /* Erzeugt eine Ganzzahl aus einem Array von Werten. Behandelt den Ueberlauf
   * bei der Erzeugung.
   */
  public Ganzzahl(int[] werte) {
    int[] tmp = Arrays.copyOf(werte, werte.length);
    int ueberlauf = 0;
    for(int i=0; i<tmp.length; i++){
      int gesamt = ueberlauf + tmp[i];
      // Java gibt bei negativen Eingaben als Ergebnis von Modulo auch einen
      // negativen Rueckgabewert, wir wollen aber Rueckgabewerte zwischen 0
      // und stellenwert haben, darum doppeltes modulo
      int hier = ((gesamt % stellenwert) + stellenwert) % stellenwert;
      ueberlauf = (gesamt-hier) / stellenwert;
      tmp[i] = hier;
      }
    int[] ret;
    if(0 == ueberlauf){
      ret = tmp;
      }else{
      ret = Arrays.copyOf(tmp, tmp.length+1);
      ret[tmp.length] = ueberlauf;
      }
    this.werte = ret;
  }

  /* Erzeuge eine zufaellige Ganzzahl mit stellen vielen Stellen.
   */
  public static Ganzzahl zufallszahl(int stellen) {
  int[] tmp = new int[stellen];
  Random rnd = new Random();
  for(int i = 0; i<stellen; i++)
    tmp[i] = rnd.nextInt(stellenwert);
  return(new Ganzzahl(tmp));
  }

  /* Gib die Zahlen aus. Die hoechstwertige Stelle zuerst.
   */
  public void show() {
    for(int i=werte.length-1; i>=0; i--)
      System.out.print(werte[i] + " ");
    System.out.println("");
  }

  /* Zaehle zwei Ganzzahlen zusammen.
   */
  public Ganzzahl plus(Ganzzahl x) {
    int len = x.werte.length;
    if(werte.length > len)
      len = werte.length;
    int[] tmp = new int[len];
    for(int i=0; i<len; i++)
      tmp[i]=0;
    for(int i=0; i<werte.length; i++)
      tmp[i]=werte[i];
    for(int i=0; i<x.werte.length; i++)
      tmp[i]+=x.werte[i];
    return(new Ganzzahl(tmp));
  }

  /* Ziehe eine Ganzzahl von einer anderen ab. Nicht definiertes Verhalten,
   * falls die abgezogene Zahl groeszer ist.
   * Wird aber nur aufgerufen, fuer Zahlen, bei denen es korrekt arbeitet.
   * Besser waere es, dies zu testen und sonst einen Fehler zu werfen, aber
   * Fehlerbehandlung ist nicht Bestandteil dieser Veranstaltung.
   */
  public Ganzzahl minus(Ganzzahl x) {
    int len = x.werte.length;
    if(werte.length > len)
      len = werte.length;
    int[] tmp = new int[len];
    for(int i=0; i<len; i++)
      tmp[i]=0;
    for(int i=0; i<werte.length; i++)
      tmp[i]=werte[i];
    for(int i=0; i<x.werte.length; i++)
      tmp[i]-=x.werte[i];
    return(new Ganzzahl(tmp));
  }

  /* Schnelle Multiplikation mit stellenwert^k
   */
  public Ganzzahl mal_stellenhoch(int k) {
  int[] tmp = new int[k+this.werte.length];
  for(int i=0; i<tmp.length; i++)
    tmp[i]=0;
  for(int i=0; i<werte.length; i++)
    tmp[i+k]=werte[i];
  return(new Ganzzahl(tmp));
  }

  /* Die kleineren k Stellen einer Zahl.
   */
  public Ganzzahl kleinestellen(int k) {
  return(new Ganzzahl(Arrays.copyOf(werte, k)));
  }

  /* Die groesseren, bis auf k Stellen einer Zahl.
   */
  public Ganzzahl grossestellen(int k) {
  int lk = werte.length - k;
  int[] tmp;
  if(lk > 0){
    tmp = new int[lk];
    for(int i=0; i<lk; i++)
      tmp[i] = werte[i+k];
    }else{
    tmp = new int[0];
    }
  return(new Ganzzahl(tmp));
  }

  /* Multipliziere eine Ganzzahl mit einem int x; x muss kleiner als der
   * Stellenwert sein.
   */
  public Ganzzahl mal_int(int x) {
  int[] tmp = new int[werte.length];
  for(int i = 0; i<werte.length; i++)
    tmp[i] = x * werte[i];
  return(new Ganzzahl(tmp));
  }

  /* Rekursive Multiplikation mit Methode 1
   */
  public Ganzzahl mal_langsam(Ganzzahl x) {
  
    //TODO: IHRE AUFGABE !!!
  
  Ganzzahl result = new Ganzzahl(0); 
    return result;
  }

  /* Rekursive Multiplikation mit Methode 2
   */
  public Ganzzahl mal_schneller(Ganzzahl x) {
  
    //TODO: IHRE AUFGABE !!!
  
    Ganzzahl result = new Ganzzahl(0); 
    return result;
  }

  /* Multipliziere zwei Zahlen mit gegebener Anzahl Stellen nach den
   * beiden Methoden. Gib aus, wie lange es gedauert hat.
   */
  public static void benchmark(int stellen) {
  System.out.println("Rechne mit " + stellen + " Stellen");
  Ganzzahl a = zufallszahl(stellen);
  Ganzzahl b = zufallszahl(stellen);
  long start = System.currentTimeMillis();
  System.out.println("Rechne langsam");
  a.mal_langsam(b);
  long langsam = System.currentTimeMillis();
  System.out.println("Rechne schneller");
  a.mal_schneller(b);
  long schneller = System.currentTimeMillis();
  System.out.println("Zeitbedarf langsam: " + (langsam - start) + " ms");
  System.out.println("Zeitbedarf schneller: " + (schneller - langsam) + " ms");
  }

  /* Teste, ob zwei Zahlen gleich sind und gib sonst eine Fehlermeldung aus.
   */
  public void printfallsungleich(String s, Ganzzahl x) {
    int len = werte.length;
    boolean falsch = false;
    if(len > x.werte.length)
      len = x.werte.length;
    for(int i = 0; i<len; i++)
      if(werte[i] != x.werte[i])
        falsch = true;
    for(int i = len; i<werte.length; i++)
      if(werte[i] != 0)
        falsch = true;
    for(int i = len; i<x.werte.length; i++)
      if(x.werte[i] != 0)
        falsch = true;
    if(falsch)
      System.out.println(s);
  }

  public static void zahltestkurz() {
    int[] kurzxval = {8,0,7,6,3};
    Ganzzahl kurzx = new Ganzzahl(kurzxval);
    int[] kurzyval = {5,2,1,7,7,1};
    Ganzzahl kurzy = new Ganzzahl(kurzyval);
    int[] kurzzval = {0,0,5,4,0,9,1,0,5,6};
    Ganzzahl kurzz = new Ganzzahl(kurzzval);
    Ganzzahl kurzxyl = kurzx.mal_langsam(kurzy);
    Ganzzahl kurzxys = kurzx.mal_schneller(kurzy);
    kurzz.printfallsungleich("kurz langsam falsch", kurzxyl);
    kurzz.printfallsungleich("kurz schneller falsch", kurzxys);
  }

  public static void zahltestmittel() {
    int[] mittelxval = {9,6,6,5,3,6,3,5,1,3,4,7,4,6,8};
    Ganzzahl mittelx = new Ganzzahl(mittelxval);
    int[] mittelyval = {9,7,4,2,1,7,8,2,6,8,6,3,4,0,3,3,8,0,1};
    Ganzzahl mittely = new Ganzzahl(mittelyval);
    int[] mittelzval = {1,5,4,3,1,8,9,1,3,1,5,7,2,2,1,0,2,1,0,9,2,5,7,0,6,3,0,0,8,7,6,3,9};
    Ganzzahl mittelz = new Ganzzahl(mittelzval);
    Ganzzahl mittelxyl = mittelx.mal_langsam(mittely);
    Ganzzahl mittelxys = mittelx.mal_schneller(mittely);
    mittelz.printfallsungleich("mittel langsam falsch", mittelxyl);
    mittelz.printfallsungleich("mittel schneller falsch", mittelxys);
  }

  public static void zahltestlang() {
    int[] langxval = {2,1,9,2,5,8,1,4,7,0,8,6,1,1,7,7,0,5,2,0,4,8,6,9,6,7,7,4,8,3,3,1,9,5,0,4,4,1,1,1,8,9,9,7,8,5,4,1};
    Ganzzahl langx = new Ganzzahl(langxval);
    int[] langyval = {0,1,8,2,9,7,5,8,9,7,7,2,0,1,6,3,7,3,7,9,0,9,2,0,5,6,6,5,0,3,1,5,5,7,8};
    Ganzzahl langy = new Ganzzahl(langyval);
    int[] langzval = {0,2,7,2,6,1,7,2,7,0,9,6,0,1,9,3,7,3,0,4,8,7,6,5,1,4,6,2,5,4,9,0,8,0,2,4,9,0,2,6,9,5,1,7,9,8,6,7,4,5,1,7,3,0,4,8,2,9,6,8,6,4,9,1,8,1,4,2,0,6,5,9,6,1,8,2,8,9,1,7,7,2,1};
    Ganzzahl langz = new Ganzzahl(langzval);
    Ganzzahl langxyl = langx.mal_langsam(langy);
    Ganzzahl langxys = langx.mal_schneller(langy);
    langz.printfallsungleich("lang langsam falsch", langxyl);
    langz.printfallsungleich("lang schneller falsch", langxys);
  }

  public static void zahltestungleich() {
    int[] ungleichxval = {5,7,5,4,4,0,0,0,6,7,1,4,0,5,9,7,2,0,0,3,5,5,8,6,4,8,6,7,7,7,8,0,7,2,0,4,0,0,6,5,9,3,7,0,9,6,5,6,4,0,8,4,5,6,8,9,5,7,8,2,2,8,3,1,5,2,3,5,9,7,4,6,1,6,8,4,3,9,3,3,5,1,4,6,7,2,2,1,0,2,0,9,5,6,1,6,6,2,1,1,2,3,2,7,8,2,8,8,9,9,0,8,8,6,2,0,3,9,3,0,2,0,1,7,7,8,9,5,3,0,0,2,7,0,0,4,6,3,3,6,9,8,8,4,2,1,2,9};
    Ganzzahl ungleichx = new Ganzzahl(ungleichxval);
    int[] ungleichyval = {2,5,2,3,7,1,0,8,9,5,9,7,1,5,5,0,1,9,7,1,4,9,8,3,5,1,2,8,9,8,9,3,9,4,7};
    Ganzzahl ungleichy = new Ganzzahl(ungleichyval);
    int[] ungleichzval = {0,0,9,7,0,7,2,2,4,1,5,8,5,5,0,0,6,5,6,6,7,2,2,8,4,6,6,9,8,3,3,5,3,7,0,0,5,0,9,2,2,3,5,6,4,6,7,9,2,1,1,6,3,3,7,3,3,8,3,6,6,7,5,2,1,0,9,1,7,2,5,7,2,0,2,6,2,0,9,1,0,1,6,0,9,6,5,9,8,1,5,7,8,4,1,7,0,1,3,1,7,2,2,9,7,8,4,0,7,1,9,6,5,8,8,3,4,8,1,8,2,2,3,0,6,7,3,5,1,4,9,3,0,0,5,9,0,9,1,9,4,4,4,4,2,5,5,5,1,3,8,9,2,7,2,0,4,9,9,0,9,5,2,9,7,1,7,0,7,9,8,4,2,2,5,8,9,2,8,3,0,9,6};
    Ganzzahl ungleichz = new Ganzzahl(ungleichzval);
    Ganzzahl ungleichxyl = ungleichx.mal_langsam(ungleichy);
    Ganzzahl ungleichxys = ungleichx.mal_schneller(ungleichy);
    ungleichz.printfallsungleich("ungleich langsam falsch", ungleichxyl);
    ungleichz.printfallsungleich("ungleich schneller falsch", ungleichxys);
  }

  public static void main(String[] args) {
  // Eine Reihe von Tests, um zu pruefen, ob korrekt gerechnet wird
  zahltestkurz();
  zahltestmittel();
  zahltestlang();
  zahltestungleich();

  // Einige Ablaeufe, um die Geschwindigkeit zu testen
  benchmark(10);
  benchmark(100);
  benchmark(1000);
  benchmark(3000);
  benchmark(10000);
  benchmark(20000);
  benchmark(40000);
  }

}

Artikelaktionen


Funktionsleiste