/*
Datei............: Aufg0727.java
Projekt..........: Einführung in die Java-Programmierung
Erstellt.........: 03.11.97, Guido Krüger
Geändert.........: --
Aufgabe..........: Musterlösung zu Aufgabe 07.27
Kommentare.......:

Die hier vorgestellte Klasse BigInteger erlaubt das Speichern
von großen Ganzzahlen und stellt Methoden für die Addition 
und Subtraktion zweier BigInteger-Objekte zur Verfügung. Die
Klasse verwendet ein Array digits[] mit 50 Elementen des Typs
byte zur Speicherung der Ziffern der Ganzzahl. In digits[0]
steht immer die höchstwertige Ziffer, in digits[49] die
nidrigwertigste. Falls eine Nummer kleiner als 0 ist, wird
das Negativflag gesetzt, ist sie 0, das Nullflag.

Die Klasse BigInteger enthält eine statische Methode testStub,
die eine Reihe von Tests durchführt. Sie erzeugt zunächst eine
Reihe von BigInteger-Objekten, zeigt sie an und führt einige
einfache Additionen und Subtraktionen darauf aus. Anschließend
werden die arithmetischen Funktionen einem Härtetest unterzogen.
Dazu werden jeweils zwei, per Zufallszahlengenerator erzeugte
Werte, addiert oder subtrahiert und mit dem Ergebnis der
eingebauten ganzzahligen Operatoren verglichen. Gibt es eine
Abweichung, schlägt das Programm Alarm. Das Programm kann durch
Drücken von STRG+C beendet werden.
*/
import java.io.*;

public class Aufg0727
{
  public static void main(String args[])
  {
	BigInteger.testStub();
  }
}

class BigInteger
{
  //--- Konstanten ----------------------------------------------
  static final int MAXDIGITS = 50;

  //--- Instanzvariablen ----------------------------------------
  private byte[]  digits;     //digits array
  private boolean zero;       //zero indicator
  private boolean negative;   //negative indicator

  //--- Öffentliche Methoden ------------------------------------
  /**
   * Erzeugt ein BigInteger-Objekt aus einem syntaktisch korrekten
   * String, der eine Ganzzahl in der Form "[+|-]n{n}" repräsentiert.
   * Das Byte Array wird immer vollkommen gefüllt, kleinere Zahlen
   * werden links mit Nullen aufgefüllt. Das Flag negative zeigt an,
   * ob es sich um eine negative Zahl handelt und zero ist gesetzt,
   * wenn der übergebene Wert 0 ist.
   */
  public BigInteger(String s)
  {
	char c;
	int  pos = MAXDIGITS - 1;

	digits   = new byte[MAXDIGITS];
	negative = false;
	zero     = true;
	s.trim();
	for (int i = s.length() - 1; i >= 0; --i) {
	  c = s.charAt(i);
	  if (c == '-') {
		negative = true;
	  } else if (c == '+') {
		//nichts
	  } else {
		digits[pos--] = (byte)(c - '0');
		if (c != '0') {
		  zero = false;
		}
	  }
	}
	while (pos >= 0) {
	  digits[pos--] = 0;
	}
  }

  /**
   * Erzeugt ein BigInteger-Objekt aus dem übergebenen long.
   */
  public BigInteger(long i)
  {
	this("" + i);
  }

  /**
   * Erzeugt ein BigInteger-Objekt aus dem übergebenen double, der
   * zuvor in eine Ganzzahl umgewandelt wird.
   */
  public BigInteger(double x)
  {
	this("" + (long)x);
  }

  /**
   * Liefert eine Stringdarstellung des BigInteger-Objekts. Führende
   * Nullen werden unterdrückt.
   */
  public String toString()
  {
	String ret;
	int i;

	if (zero) {
	  ret = "0";
	} else {
	  ret = negative ? "-" : "";
	  //führende Nullen überspringen
	  for (i = 0; i < MAXDIGITS; ++i) {
		if (digits[i] != 0) {
		  break;
		}
	  }
	  //signifikante Ziffern anhängen
	  while (i < MAXDIGITS) {
		ret += (char)(digits[i++] + '0');
	  }
	}
	return ret;
  }

  /**
   * Vergleicht den absoluten Wert zweier BigInteger-Objekte.
   * Gibt einen Wert kleiner als 0, gleich 0 oder größer als 0
   * zurück, abhängig davon, ob das eigene Objekt kleiner, gleich
   * oder größer num ist.
   */
  public int absoluteCompareTo(BigInteger num)
  {
	for (int i = 0; i < MAXDIGITS; ++i) {
	  if (digits[i] < num.digits[i]) {
		return -1;
	  } else if (digits[i] > num.digits[i]) {
		return 1;
	  }
	}
	return 0;
  }

  /**
   * Addiert zwei BigInteger-Objekte
   */
  public static BigInteger add(BigInteger num1, BigInteger num2)
  {
	BigInteger ret;

	if (num1.zero) {
	  ret = new BigInteger(num2.toString());
	} else if (num2.zero) {
	  ret = new BigInteger(num1.toString());
	} else if (num1.negative == num2.negative) {
	  ret = simpleAddition(num1,num2);
	  ret.negative = num1.negative;
	} else {
	  BigInteger tmp1, tmp2;
	  if (num1.negative) {
		tmp1 = num2;
		tmp2 = num1;
	  } else {
		tmp1 = num1;
		tmp2 = num2;
	  }
	  if (tmp1.absoluteCompareTo(tmp2) < 0) {
		ret = simpleSubtraction(tmp2,tmp1);
		ret.negative = true;
	  } else {
		ret = simpleSubtraction(tmp1,tmp2);
		ret.negative = false;
	  }
	}
	return ret;
  }

  /**
   * Subtrahiert zwei BigInteger-Objekte.
   */
  public static BigInteger subtract(BigInteger num1, BigInteger num2)
  {
	BigInteger tmp = new BigInteger(num2.toString());
	tmp.negative = !tmp.negative;
	return add(num1,tmp);
  }

  //--- Private Methoden ----------------------------------------
  /**
   * Führt eine vorzeichenlose Addition zwei BigInteger-Objekte durch.
   */
  private static BigInteger simpleAddition(BigInteger num1, BigInteger num2)
  {
	int i, sum, carry;
	BigInteger ret = new BigInteger(0);

	carry = 0;
	for (i = MAXDIGITS - 1; i >= 0; --i) {
	  sum = num1.digits[i] + num2.digits[i] + carry;
	  ret.digits[i] = (byte)(sum % 10);
	  carry = (sum >= 10) ? 1 : 0;
	  if (sum % 10 > 0) {
		ret.zero = false;
	  }
	}
	return ret;
  }

  /**
   * Führt eine vorzeichenlose Subtraktion zwei BigInteger-Objekte durch.
   */
  private static BigInteger simpleSubtraction(BigInteger num1, BigInteger num2)
  {
	int i, sum, carry;
	BigInteger ret = new BigInteger(0);

	carry = 0;
	for (i = MAXDIGITS - 1; i >= 0; --i) {
	  sum = 10 + num1.digits[i] - num2.digits[i] - carry;
	  ret.digits[i] = (byte)(sum % 10);
	  carry = (sum < 10) ? 1 : 0;
	  if (sum % 10 > 0) {
		ret.zero = false;
	  }
	}
	return ret;
  }

  //--- Testcode ------------------------------------------------
  private String internalRepresentation()
  {
	String s = "";
	for (int i = 0; i< MAXDIGITS; ++i) {
	  s += digits[i];
	}
	if (zero) {
	  s += " zero";
	}
	if (negative) {
	  s += " negative";
	}
	return s;
  }

  static void testStub()
  {
	//basic tests
    BigInteger i1 = new BigInteger(0);
    BigInteger i2 = new BigInteger(13528);
    BigInteger i3 = new BigInteger(-436);
    BigInteger i4 = new BigInteger("1000000000");
    BigInteger i5 = new BigInteger("-1000000000");
    System.out.println("i1 = "+i1.internalRepresentation());
    System.out.println("i2 = "+i2.internalRepresentation());
    System.out.println("i3 = "+i3.internalRepresentation());
    System.out.println("i4 = "+i4.internalRepresentation());
    System.out.println("i5 = "+i5.internalRepresentation());
    System.out.println("i1 = "+i1.toString());
    System.out.println("i2 = "+i2.toString());
    System.out.println("i3 = "+i3.toString());
    System.out.println("i4 = "+i4.toString());
    System.out.println("i5 = "+i5.toString());
	System.out.println("i1 + i2 = "+BigInteger.add(i1,i2).toString());
	System.out.println("i1 + i3 = "+BigInteger.add(i1,i3).toString());
	System.out.println("i2 + i3 = "+BigInteger.add(i2,i3).toString());
	System.out.println("i3 + i2 = "+BigInteger.add(i3,i2).toString());
	System.out.println("i2 + i4 = "+BigInteger.add(i2,i4).toString());
	System.out.println("i4 + i2 = "+BigInteger.add(i4,i2).toString());
	System.out.println("i1 - i2 = "+BigInteger.subtract(i1,i2).toString());
	System.out.println("i1 - i3 = "+BigInteger.subtract(i1,i3).toString());
	System.out.println("i2 - i3 = "+BigInteger.subtract(i2,i3).toString());
	System.out.println("i3 - i2 = "+BigInteger.subtract(i3,i2).toString());
	System.out.println("i2 - i4 = "+BigInteger.subtract(i2,i4).toString());
	System.out.println("i4 - i2 = "+BigInteger.subtract(i4,i2).toString());
	//Zufallstests
	System.out.println("Starten der Zufallstests...");
	java.util.Random rand = new java.util.Random();
	BigInteger num1, num2, res;
	int n1, n2, cnt = 0;
	while (true) {
	  if (cnt % 100 == 0) {
		System.out.println("Erfolgreiche Tests: "+cnt);
	  }
	  ++cnt;
	  num1 = new BigInteger((n1 = rand.nextInt() % 1000000000));
	  num2 = new BigInteger((n2 = rand.nextInt() % 1000000000));
	  if (rand.nextInt() >= 0) {
		res = BigInteger.add(num1,num2);
		if (Integer.parseInt(res.toString()) != n1 + n2) {
          System.out.println(
			"error adding "+n1+" + "+n2+
			" add: "+res.toString()+
			" +: "+(n1 + n2)
		  );
		}
	  } else {
		res = BigInteger.subtract(num1,num2);
		if (Integer.parseInt(res.toString()) != n1 - n2) {
		  System.out.println(
			"error subtracting "+n1+" - "+n2+
			" subtract: "+res.toString()+
			" -: "+(n1 - n2)
		  );
		}
	  }
	}
  }
}