public class Polynom {
  private double[] koeffizienten;

  public Polynom(double[] koeff) {
    koeffizienten=koeff.clone();
  }

  public int ord() {
    return koeffizienten.length;
  }

  public int deg() {
    return koeffizienten.length-1;
  }

  public boolean isZero() {
    return (koeffizienten.length==1 && koeffizienten[0]==0);
  }

  public double auswerten(double stelle) {
    double rval=0;
    for(int i=koeffizienten.length-1; i>=0; i--) {
      rval=koeffizienten[i]+stelle*rval;
    }
    return rval;
  }

  public double koeffizient(int offset) {
    return koeffizienten[offset];
  }

  public String toString() {
    String s="";
    int i;
    for (i=koeffizienten.length-1; i>0; i--) {
      s+=Double.toString(koeffizienten[i])+"x^"+Integer.toString(i)+" + ";
    }
    s+=Double.toString(koeffizienten[0]);
    return s;
  }

  public double[] toDoubleArray() {
    return koeffizienten.clone();
  }

  public Polynom div(Polynom divisor) {
    double[] neueKoeffizienten, restPolynom, tempPolynom;
    double faktor;
    int i;
    if(koeffizienten.length < divisor.ord()) return new Polynom(new double[] {0});
    neueKoeffizienten=new double[koeffizienten.length - divisor.ord() + 1];
    restPolynom=koeffizienten.clone();
    do {
      faktor=restPolynom[restPolynom.length-1]/divisor.koeffizient(divisor.ord()-1);
      neueKoeffizienten[restPolynom.length - divisor.ord()]=faktor;
      for(i=1;i<=divisor.ord();i++) {
        restPolynom[restPolynom.length-i]-=faktor*divisor.koeffizient(divisor.ord()-i);
      }
      while(restPolynom.length > 0 && restPolynom[restPolynom.length-1]==0) {
        tempPolynom=new double[restPolynom.length-1];
        System.arraycopy(restPolynom,0,tempPolynom,0,restPolynom.length-1);
        restPolynom=tempPolynom;
      }
    } while (restPolynom.length >= divisor.ord());
    return new Polynom(neueKoeffizienten);
  }

  public Polynom mod(Polynom divisor) {
    double[] restPolynom, tempPolynom;
    double faktor;
    int i;
    if(koeffizienten.length < divisor.ord()) return new Polynom(koeffizienten);
    restPolynom=koeffizienten.clone();
    do {
      faktor=restPolynom[restPolynom.length-1]/divisor.koeffizient(divisor.ord()-1);
      for(i=1;i<=divisor.ord();i++) {
        restPolynom[restPolynom.length-i]-=faktor*divisor.koeffizient(divisor.ord()-i);
      }
      while(restPolynom.length > 0 && restPolynom[restPolynom.length-1]==0) {
        tempPolynom=new double[restPolynom.length-1];
        System.arraycopy(restPolynom,0,tempPolynom,0,restPolynom.length-1);
        restPolynom=tempPolynom;
      }
    } while(restPolynom.length >= divisor.ord());
    if(restPolynom.length==0)return new Polynom(new double[] {0});
    else return new Polynom(restPolynom);
  }

  public static Polynom ggt(Polynom a, Polynom b) {
    Polynom r;
    r=a.mod(b);

    if(r.ord()==1) return r; // Hinzugefügt um teilerfremde Polynome abzudecken
    if(r.isZero()) return b;
    else return ggt(b,r);
  }
}