var TT="",ERR=(1==0);

function ggtp()
{
	//var p1=new Array(5,-7,1,1),p0=new Array(-4,0,3),p2=new Array(3,0,-2);
	//var p3=polymult(p1,p0),p4=polymult(p2,p0);gf=new Array(0,0);
	//var u=new Array(-5,2,8,-3,-3,0,1,0,1),v=new Array(21,-9,-4,0,5,0,3);

	ERR=false;
	var t,kr1=new Array(),kr2=new Array(),g1,p1,g2,p2,k1=new Array(),k2=new Array(),kk1=new Array(),kk2=new Array();
	document.f.t3.value=document.f.t3b.value=document.f.t4.value="Rechne...";
	parsePolynomR(document.f.t1.value,"x",kr1);
	parsePolynomR(document.f.t2.value,"x",kr2);
	p1=kr1[0].n;g1=(kr1.length>1)?p1:1;p2=kr2[0].n;g2=(kr2.length>1)?p2:1;
	for(i=1;i<kr1.length;i++){p1*=kr1[i].n;g1=ggT(g1,kr1[i].n);}
	for(i=1;i<kr2.length;i++){p2*=kr2[i].n;g2=ggT(g2,kr2[i].n);}
	var f=new RationaleZahl(p1*p2/g1/g2,1);//alert(p2);
	for(i=0;i<kr1.length;i++){kr1[i].mult(f);kk1[i]=k1[i]=kr1[i].z;}
	for(i=0;i<kr2.length;i++){kr2[i].mult(f);kk2[i]=k2[i]=kr2[i].z;}
	var g=(document.f.algo.selectedIndex==0)?ggTp1(k1,k2,true):((g==1)?ggTp2(k1,k2,true):ggTp3(k1,k2));
	TT=(document.f.t3.value="  "+pstr(g)+((ERR&&(g<2))?"    ———> mφglicherweise Fehler wegen Ganzzahlόberlaufs <———":""));
	TT+="\n"+(t=document.f.t4.value=br(k1,k2," "));
	var kgv=new Array(),r=new Array(),q=new Array(); polydiv(polymult(kk1,kk2),g,kgv,r);
	document.f.t3b.value=(isNullpoly(r))?"  "+pstr(kgv):"  Fehler unbekannter Ursache";
	
	var g1=getGrad(k1),g2=getGrad(k2);
	if((g1<g2)||(pstr(k2)=="1")||(pstr(k2)=="-1"))return;
	document.f.t4.value+="  Rechne...";
	Q=new Array();
	polydivR(k1,k2,Q,r);
	var gza=" ";
	for(i=Q.length-1;i>=0;i--)gza+=(Q[i].z!=0)?Q[i].str()+((i>1)?"x^"+i:(i==1)?"x":"")+" + ":"";
	gza=gza.replace(/ \+ -/g," - ").replace(/ 1x/g," x").replace(/-1x/g,"-x");
	var T=t.split("\n");
	var ra=(!isNullpoly(r))? br(r,k2,"",true).split("\n"): new Array("","","");
	T[1]+="  = "+gza;
	T[0]+=space.substr(0,T[1].length-T[0].length);
	T[2]+=space.substr(0,T[1].length-T[2].length);

	T[0]+=ra[0];T[1]+=ra[1];T[2]+=ra[2];
	document.f.t4.value=T.join(" \n").replace(/\+  \n/,"   \n");
}

function bsp()
{
	do
	{
	var n0=Math.floor(Math.random()*3+2),n1=Math.floor(Math.random()*5+2),n2=Math.floor(Math.random()*5+2);
	var k0=new Array(),k1=new Array(),k2=new Array(),p1=new Array(),p2=new Array();
	var i;
	do{for(i=0;i<n0;i++)k0[i]=Math.round((Math.random()-0.5)*12);if((i<n0-1)&&(Math.random()>.3))k0[i]=0;}while(isNullpoly(k0));
	do{for(i=0;i<n1;i++)k1[i]=Math.round((Math.random()-0.5)*12);if((i<n1-1)&&(Math.random()>.3))k1[i]=0;}while(isNullpoly(k1));
	do{for(i=0;i<n2;i++)k2[i]=Math.round((Math.random()-0.5)*12);if((i<n2-1)&&(Math.random()>.3))k2[i]=0;}while(isNullpoly(k2));
	//document.f.t5.value=(pstr(k0)+"\n"+pstr(k1)+"\n"+pstr(k2))+"\n";
	p1=polymult(k0,k1);p2=polymult(k0,k2);
	//document.f.t5.value+=pstr(p1)+"\n"+pstr(p2);
	document.f.t1.value=pstr(p1);document.f.t2.value=pstr(p2);
	ggtp();
	}while((TT.indexOf("NaN")>-1)||(TT.indexOf("Fehler")>-1));
}

var space="                                                                                                             ";
space+=space;space+=space;space+=space;
var brstr="———————————————————————————————————————————————————————————————";
brstr+=brstr;brstr+=brstr;brstr+=brstr;
function br(k1,k2,inc,auskl)
{	
	if((k1[getGrad(k1)]<0)&&(k2[getGrad(k2)]<0)){for(i=0;i<k1.length;i++)k1[i]=-k1[i];for(i=0;i<k2.length;i++)k2[i]=-k2[i];}
	if(pstr(k2)=="1")return "  "+"\n "+inc+pstr(k1)+"\n  ";
	if(pstr(k2)=="-1"){for(var i=0;i<k1.length;i++)k1[i]=-k1[i];return inc+pstr(k1);}
	if(inc==null)inc="";
	var z=pstr(k1),n=pstr(k2),i;
	if(auskl==true)
	{
		var kk1=new Array(),c,kk2=new Array();
		c=cont(k1);if(Math.abs(c)!=1){for(i=0;i<k1.length;i++)kk1[i]=k1[i]/c;z=c+"·("+pstr(kk1)+")";}
		z=z.replace(/·\(1\)/,"").replace(/·\(x\)/,"x");
		c=cont(k2);if(Math.abs(c)!=1){for(i=0;i<k2.length;i++)kk2[i]=k2[i]/c;n=c+"·("+pstr(kk2)+")";}
		n=n.replace(/·\(1\)/,"").replace(/·\(x\)/,"x");
	}
	var lz=z.length,ln=n.length,lm=Math.max(ln,lz),dz=lm-lz,dn=lm-ln;
	return inc+space.substr(0,1+Math.round(dz/2+.2))+z+space.substr(0,1+Math.floor(dz/2))+"\n"+inc+brstr.substr(0,lm+2)+"\n"+inc+space.substr(0,1+Math.round(dn/2+.1))+n+space.substr(0,1+Math.floor(dn/2));
}

//k1,k2 Koeffizienten, kz=kόrzen?
function ggTp1(k1,k2,kz)
{
	var c1=cont(k1),c2=cont(k2),c3,d=ggT(c1,c2);
	var u=new Array(k1.length),v=new Array(k2.length),i;
	for(i=0;i<k1.length;i++)u[i]=k1[i]/c1;
	for(i=0;i<k2.length;i++)v[i]=k2[i]/c2;
	var ii=0;
	do
	{
		r=pseudopolydiv(u,v);
		if(isNullpoly(r))break;
		if(getGrad(r)==0){v=new Array(1,0);break;}
		u=Clone(v);
		c3=cont(r);for(i=0;i<r.length;i++)r[i]/=c3;
		v=Clone(r);
		ii++;
	}while(ii<100);
	for(i=0;i<v.length;i++)v[i]*=d;
	if(!kz)return v;
	var r=new Array(),q=new Array();
	polydiv(k1,v,k1,r);//for(i=0;i<q.length;i++)k1[i]=q[i];for(i=q.length;i<k1.length;i++)k1[i]=0;
	polydiv(k2,v,k2,r);//for(i=0;i<q.length;i++)k2[i]=q[i];for(i=q.length;i<k2.length;i++)k2[i]=0;
	return v;
}

function ggTp2(k1,k2,kz)
{
	var c1=cont(k1),c2=cont(k2),c3,d=Math.abs(ggT(c1,c2)),g=1,h=1;
	var u=new Array(k1.length),v=new Array(k2.length),i;
	for(i=0;i<k1.length;i++)u[i]=k1[i]/c1;
	for(i=0;i<k2.length;i++)v[i]=k2[i]/c2;
	var ii=0;
	do
	{
		//alert(u+"\n"+v+"\n"+g+"\n"+h);
		var dd=getGrad(u)-getGrad(v);
		var r=pseudopolydiv(u,v);//alert("r= "+r); 
		if(isNullpoly(r))break;
		if(getGrad(r)==0){v=new Array(1,0);break;}
		var n=(g*Math.pow(h,dd));//alert(g+"   "+h+"   "+dd+"   "+n);
		for(i=0;i<r.length;i++){if(String(r[i]).indexOf("e")>-1)ERR=true;r[i]=Math.round(r[i]/n);}
		u=Clone(v);v=Clone(r);
		g=u[getGrad(u)];
		h=(Math.pow(h,1-dd)*Math.pow(g,dd));
		ii++;
	}while(ii<50);
	c3=cont(v);
	for(i=0;i<v.length;i++)v[i]=Math.round(v[i]*d/c3);
	if(!kz)return v;
	var r=new Array(),q=new Array();
	polydiv(k1,v,k1,r);//for(i=0;i<q.length;i++)k1[i]=q[i];for(i=q.length;i<k1.length;i++)k1[i]=0;
	polydiv(k2,v,k2,r);//for(i=0;i<q.length;i++)k2[i]=q[i];for(i=q.length;i<k2.length;i++)k2[i]=0;
	return v;
}

function ggTp3(k1,k2)
{
	return pggT(k1,k2);
}

function pseudopolydiv(k1,k2)
{
	var m=getGrad(k1),n=getGrad(k2),u=new Array(m+1),k,j;
	if(m<n)return k1;
	for(k=0;k<=m;k++)u[k]=k1[k];//for(k=0;k<n+1;k++)v[k]=k2[k];
	for(var k=m-n;k>=0;k--)
	{
		for(j=n+k-1;j>=0;j--)
		{
			//alert(j+"\n"+(k2[n]*u[j])+"\n"+(k2[n]*u[j]-u[n+k]*k2[j-k]));
			u[j]=Math.round(k2[n]*u[j]-((j>=k)?u[n+k]*k2[j-k]:0));
			if(Math.abs(u[j])>1e15)ERR=true;
		}
		u[n+k]=0;
//		alert(u);
	}
	//alert("pseudodiv\n"+k1+"\n"+k2+"\n"+u);
	return Clean(u);
}

function cont(k)
{
	var gr=getGrad(k),g=k[gr];
	for(var i=gr-1;i>=0;i--){if(k[i]!=0)g=ggT(g,k[i]);}
	return Math.abs(g)*((k[gr]>0)?1:-1);
}

function ganzzahlig(k)
{
	var g=getGrad(k);
	for(var i=1;i<1000;i++)
	{
		for(var j=0;j<=g;j++)if(Math.abs(k[j]*i-Math.round(k[j]*i))>1e-10)break;
		if(j>g)
		{
			for(j=0;j<=g;j++)k[j]=Math.round(i*k[j]);
			return i;
		}
	}
	return 1;
}

function ggT(a,b)
{
	if((a==0)||(b==0))return 1;if((a%1)!=0)return 1;if((b%1)!=0)return 1;
	if(isNaN(a))return 1;if(isNaN(b))return 1;
	var c=1;while(c!=0){c=a%b;a=b;b=c;}	return a;
}

function isNullpoly(k)
{
	for(var i=0;i<k.length;i++)if((k[i]!=0)&&(k[i]!=null))return false;
	return true;
}

function polymult(a,b)
{
	var c=new Array(0,0),i,ga=getGrad(a),gb=getGrad(b);
	for(i=0;i<ga+gb;i++)c[i]=0;
	for(i=0;i<=ga;i++)
	{
		if(a[i]==0)continue;
		if(a[i]==null)continue;
		for(j=0;j<=gb;j++)
		{
			if(b[j]==0)continue;	
			if(b[j]==null)continue;	
			if(c[i+j]==null)c[i+j]=0;
			c[i+j]+=a[i]*b[j];
		}
	}
	//alert("polymult\n"+a+"\n"+b+"\n"+c);	
	return c;
}
function polyadd(a,b)
{
	var c=new Array(Math.max(a.length,b.length)),i;
	for(i=0;i<c.length;i++)
	{
		c[i]=(a[i]!=null)?a[i]:0;
		c[i]+=(b[i]!=null)?b[i]:0;
	}
	return c;
}
function polyaddb(z1,n1,z2,n2,z,n,i)
{
	var zz=new Array();
	zz=polyadd(polymult(z1,n2),polymult(z2,n1));
	n[i]=polymult(n1,n2);
	z[i]=zz;
}
function polysub(a,b)
{
	var c=new Array(Math.max(a.length,b.length)),i;
	for(i=0;i<c.length;i++)
	{
		c[i]=(a[i]!=null)?a[i]:0;
		c[i]-=(b[i]!=null)?b[i]:0;
	}
	return c;
}
function polydiv(z,n,q,r)
{
	z=Clone(z);n=Clone(n);
	var gz=getGrad(z),gn=getGrad(n),m=n[gn],f,i,d,j=0,fn=new Array();
	//r=new Array(gz+1);
	for(i=0;i<=gz;i++){r[i]=z[i];q[i]=0;}
	//if(gn==0){for(i=0;i<=gz;i++)q[i]=z[i]/n[0];return;}
	while((gz>=gn)&&(j<50))
	{
		d=gz-gn;
		f=r[gz]/m;
		for(i=0;i<=gn;i++)r[i+d]-=f*n[i];
		r[gz]=0;
		q[d]+=f;
	//	alert("Rest: "+PStr("x",r)+"\n\nDivisor: "+PStr("x",n)+"\n\nQuotient: "+PStr("x",q));
		j++;
		gz=getGrad(r);
	}
	for(i=0;i<q.length;i++)if(q[i]==null)q[i]=0;
	for(i=0;i<r.length;i++)if(r[i]==null)r[i]=0;
	//alert("polydiv:\n"+pstr(z)+"\n"+pstr(n)+"\n"+pstr(q)+"\n"+pstr(r));
}
function polydivR(Z,N,q,R)
{	
	var gz=getGrad(Z),gn=getGrad(N);
	var r=new Array(gz+1),n=new Array(gn+1),i;
	for(i=0;i<=gz;i++){r[i]=new RationaleZahl(Z[i],1);q[i]=new RationaleZahl(0,1);}
	for(i=0;i<=gn;i++)n[i]=new RationaleZahl(N[i],1);
	if(gn==0){for(i=0;i<=gz;i++){q[i].set(Z[i],N[0]);q[i].kuerzen();if(q[i].n<0){q[i].n=-q[i].n;q[i].z=-q[i].z;}r[i]=0;}return;}
	var m=new RationaleZahl(n[gn].z,1),f=new RationaleZahl(0,1),d,j=0,fn=new Array();
	var e=new RationaleZahl();
	while((gz>=gn)&&(j<50))
	{
		d=gz-gn;
		f.setR(r[gz]);f.div(m);
		for(i=0;i<=gn;i++){e.setR(f);e.mult(n[i]);r[i+d].sub(e);}
		r[gz].set(0,1);
		q[d].add(f);
	//	alert("Rest: "+PStr("x",r)+"\n\nDivisor: "+PStr("x",n)+"\n\nQuotient: "+PStr("x",q));
		j++;
		gz--;
	}
	//for(i=0;i<q.length;i++)if(q[i]==null)q[i]=0;
	//for(i=0;i<r.length;i++)if(r[i]==null)r[i]=0;
	//alert("polydiv:\n"+pstr(z)+"\n"+pstr(n)+"\n"+pstr(q)+"\n"+pstr(r));
	var p=1;for(i=0;i<r.length;i++){if(r[i].z!=0)p*=r[i].n;R[i]=r[i].z;}
	for(i=0;i<r.length;i++)if(r[i].z!=0)R[i]*=p/r[i].n;
	for(i=0;i<N.length;i++)N[i]*=p;
	var ggt=ggT(cont(R),cont(N));//alert(R+"\n"+N);
	for(i=0;i<R.length;i++)R[i]/=ggt;
	for(i=0;i<N.length;i++)N[i]/=ggt;
}

function ableitung(k,n)
{
	var p=Clone(k);
	if(n==null)n=1;var g=getGrad(k);
	for(i=0;i<n;i++){for(j=0;j<g;j++)p[i]=(i+1)*p[i+1];p[g]=0;}
	return Clean(p);
}

function getGrad(k)
{
	for(var i=k.length-1;i>=0;i--)
	{
		if(k[i]!=0)break;
	}
	return i;
}

function Clean(k)
//Verkleinert Koeffizienten-Array auf richtigen Bereich
{
	var m=k.length-1;
	while(((Math.abs(k[m])<0.000000000001)||(isNaN(k[m])||(k[m]=="")))&&(m>0))m--;
	var kk=new Array(m+1);
	for(i=0;i<m+1;i++)
	{
		kk[i]=k[i];if((kk[i]=="")||(isNaN(kk[i])))kk[i]=0.0;
		if(Math.abs(kk[i])<0.00000000001) kk[i]=0 ;
	}
	//alert("Clean\nvorher: "+k+"\nnachher: "+kk);
	return kk;
}

function Clone(k)
{
	var kk=new Array(k.length)
	for(i=0;i<k.length;i++)kk[i]=k[i];
	return kk;
}