// Javascript zur Polynomdivision
// (c) Arndt Brünner, Gelnhausen, 2. 11. 2002
// Version: 3. 11. 2002
// Alle Rechte vorbehalten!


var vorherkuerzen=(1==2);
//A, B: Array mit RationalenZahlen für Koeffizienten von Dividend und Divisor
//C[i]: q*B[i]
//q als RationaleZahl für Koeffizient des Quotienten
//gibt Exponent des Quotienten zurück bzw. -1 für Abbruch
function polydivstep(A,B,C,q)
{
	var i,k,am=-1,bm=-1;
	am=getMaxKoeff(A);
	if(am==-1){q.set(0,1);return -1;}
	bm=getMaxKoeff(B);
	if((bm>am)||(bm==-1)){q.set(0,1);return-1;}
	k=am-bm;
	q.set(A[am].z,A[am].n);
	var d=new RationaleZahl(1,1);
	q.div(B[bm]);
	//alert("q = "+q.str());
	for(i=0;i<=bm;i++)
	{
		A[i+k].sub(d.set(B[i].z*q.z,B[i].n*q.n));
		C[i+k].set(d.z,d.n);C[i+k].kuerzen(0);
		//alert((i+k)+"  "+A[i+k].str()+"\n"+B[i].n+"  "+q.n);
	}
	for(i=bm+1+k;i<C.length;i++)C[i].set(0,1);
	return k; //Exponent
}

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

var A=new Array(10),B=new Array(10),Q=new Array(10),C=new Array(10);
var B1=new RationaleZahl(1,1),B0=new RationaleZahl(0,1);
for(var i=0;i<A.length;i++){A[i]=new RationaleZahl(0,1);B[i]=new RationaleZahl(0,1);C[i]=new RationaleZahl(0,1);Q[i]=new RationaleZahl(0,1);}

function polydiv(p0,p1)
{
	var q=new RationaleZahl(0,1);
	var t="",T="",TT="",TTT="",TTTT="",TTTTT="";
	document.f.p2.value="";
	document.f.Erkl.value="";
	vorherkuerzen=document.f.vorherkuerzen.checked;
	p0=p0.toLowerCase().replace(/,/g,".").replace(/ /g,"").replace(/:/g,"/");
	p1=p1.toLowerCase().replace(/,/g,".").replace(/ /g,"");
	if(p0.indexOf(")/(")>-1){var PP=p0.split(")/(");p0=PP[0].replace(/\(/,"");p1=PP[1].replace(/\)/,"");}
	if((p0=="")||(p1==""))return "Eingabe fehlt";
	if((p0.indexOf("(")>-1)||(p0.indexOf("(")>-1)){alert("Klammerung wird leider nicht unterstützt!");return;}
	var VV=new Array(0),atab=new Array(),ntab=0,mtab=0;

	status="extrahiere Variablen";
	extractVars(p0+" "+p1,VV);
	if(VV.length>1)
	{
		document.f.Erkl.value="Es wird der Algorithmus für die Division algebraischer Summen verwendet, da andere \nVariablen außer x auftreten. Keine detaillierten Erläuterungen verfügbar.";
		var vrs=document.f.vars.value;
		VV=new Array(0);
		if(vrs!="")VV=vrs.replace(/,/g,"").replace(/ +/g,"").replace(/\d/g,"").split("");
		t=divAlgSums(p0,p1,VV);
		document.f.vars.value=VV.join(" ");
		if(t=="")document.f.vars.value="";
		document.f.Erkl.value=EA;
		document.f.Erkltab.value=" \n für mehrere Variablen noch nicht verfügbar";
		return t;
	}
	if((VV.length==1)&&(VV[0]!="x"))
	{
		var iV;
		do{iV=p0.indexOf(VV[0]);if(iV==-1)break;p0=p0.substr(0,iV)+"x"+p0.substring(iV+1,p0.length);}while(true);
		do{iV=p1.indexOf(VV[0]);if(iV==-1)break;p1=p1.substr(0,iV)+"x"+p1.substring(iV+1,p1.length);}while(true);
	}

	status="lese und übersetze Eingaben: Dividend";
	for(i=0;i<Q.length;i++){Q[i].set(0,1);B[i].set(0,1);A[i].set(0,1);C[i].set(0,1);}
	parsePolynom(p0,"x",A);
	p0=PStr("x",A);
	var am=getMaxKoeff(A);
	if(am>100)
	{
		status="";
		return "Das Script ist beschränkt auf Summanden bis x^100\n\n";
	}
	status="erzeuge bzw. erweitere Arrays";
	if(am>Q.length-1)for(ii=Q.length;ii<=am;ii++)Q[ii]=new RationaleZahl(0,1);
	if(am>B.length-1)for(ii=B.length;ii<=am;ii++)B[ii]=new RationaleZahl(0,1);
	if(am>C.length-1)for(ii=C.length;ii<=am;ii++)C[ii]=new RationaleZahl(0,1);
	status="lese und übersetze Eingaben: Divisor";
	parsePolynom(p1,"x",B);
	var bm=getMaxKoeff(B);
	if(bm<0){status="";return "Fehler im Divisor";}
	p1=PStr("x",B);
	if(p1=="0"){status="";return "Division durch 0";}
	document.f.p0.value=p0.replace(/x/g,VV[0]);//.replace(/\^2 /g,"² ").replace(/\^3 /g,"³ ");
	document.f.p1.value=p1.replace(/x/g,VV[0]);//.replace(/\^2 /g,"² ").replace(/\^3 /g,"³ ");

	T="";
	if(vorherkuerzen)
	{
		t=kuerzen(A,am,B,am);
		if((t!="")&&(t!="1"))
		{
			T+="Kürze die Polynome zunächst mit "+t+":\n";
			T+=(p0=PStr("x",A))+"\n"+(p1=PStr("x",B))+"\n\n";
			am=getMaxKoeff(A);bm=getMaxKoeff(B);
		}
	}
	t="";
	TTTT=B[bm].str();
	if((TTTT=="1")&&(bm>0))TTTT="";
	if((TTTT=="-1")&&(bm>0))TTTT="-";
	TTTT+=((bm>0)?"x"+((bm>1)?"^"+bm:""):"");
	if(B[bm].z<0)TTTT="("+TTTT+")";
	TTTTT=TTTT;
	if((TTTT!="x")&&(TTTT.indexOf("x")>-1)&&(TTTT.charAt(0)!="("))TTTTT="("+TTTTT+")";

	if(bm==0)
	{
		T+="Man teilt ein Polynom durch eine Zahl, indem man jeden Koeffizienten\n";
		T+="des Polynoms durch diese Zahl dividiert.\n\n";
		if(B[0].n==B[0].z)T+="Die Division durch 1 verändert nichts.\n\n";
		if(B[0].n==-B[0].z)T+="Die Division durch -1 ist äquivalent zur Multiplikation mit -1.\nAlle Koeffizienten wechseln das Vorzeichen.\n\n";
		for(i=0;i<=am;i++)A[i].div(B[0]);
		document.f.Erkl.value=(T);
		document.f.Erkltab.value="";
		status="";
		return PStr("x",A);
	}

	T+="Wie bei der schriftlichen Division von Zahlen zieht man auch bei der Polynomdivision\n";
	T+="vom Dividenden nach und nach passende Vielfache des Divisors ab, bis am Ende möglichst\n";
	T+="kein Rest mehr bleibt. Dazu wird in jedem Schritt derjenige Summand des Restes elimi-\n";
	T+="niert, bei dem x in der höchsten Potenz steht.\n";
	T+="Die Summanden des Quotienten erhält man daher durch Division dieses Summanden der \njeweiligen Reste durch den ";
	T+="Summanden des Divisors mit der höchsten Potenz von x. \n";
	T+="In diesem Beispiel ist das "+TTTT.replace(/\(/,"").replace(/\)/,"")+".\n\n";
	T+="Betrachte den Dividenden "+p0+" als ersten \"Rest\".\n\n";
	ntab=1;atab[0]=p0;mtab=getMaxKoeff(A);
	var i=-1,ii=-1,iRest="erste",I=0;
	do{
		am=getMaxKoeff(A);
		status="Polynomdivision und Kommentarerzeugung laufen. Grad des Restpolynoms: "+am;
		if(am>-1)TTT=A[am].str()+((am>0)?"x"+((am>1)?"^"+am:""):"");
		i=polydivstep(A,B,C,q);
		if((i==-1)||(i==ii))break;
		TT=q.str()+((i>0)?"x"+((i>1)?"^"+i:""):"");
		T+="Der Summand dieses Restes mit der höchsten Potenz von x ist "+TTT+".\n";
		T+="Da "+TTT+"/"+TTTTT+" = "+TT+", "
		T+="ist der "+iRest+" Summand des Quotienten "+(TT)+".\n";
		iRest="nächste";
		T+="Berechne "+TT+"·("+PStr("x",B)+") = "+(atab[ntab++]=PStr("x",C))+"\n";//alert(PStr("x",C));
		T+="und subtrahiere dies vom letzten Rest. \n-> neuer Rest: "+(atab[ntab++]=PStr("x",A))+"\n\n";
		Q[i].set(q.z,q.n);
		if((q.n>1.0e+15)||(Math.abs(q.z)>1.0e+15))
		{
			T+="\n   ABBRUCH: Zahlen zu groß (>10^15)\n\n";
			I=10000;
			break;
		}
		ii=i;I++;
		t+=q.str()+"·x^"+i;
		if(I>100){T+="\n   FEHLER - ABBRUCH\n   (mehr als 100 Durchgänge)\n\n"; return "?";}
	}while(i>-1);
	status="Polynomdivision abgeschlossen. Formatiere Ausgabe";
	if((am>-1)&&(I<101))
	{
		T+="Der Rest hat einen kleineren Polynomgrad (g="+am+") als der Divisor (g="+bm+") -> Abbruch\n\n";
		T+="Der Quotient wird ergänzt durch den Summanden \"Rest/Divisor\".\n\n";
	}
	else if(I<101)
	{
		T+="Kein Rest -> Abbruch\n\n";
	}
	//alert(t);
	var ta=PStr("x",A);
	am=getMaxKoeff(A);
	if((am==0)&&(A[0].n!=1))
	{
		for(i=0;i<B.length;i++){B[i].z*=A[0].n;B[i].kuerzen();}
		A[0].n=1;ta=A[0].z;
	}
	bm=getMaxKoeff(B);
	if(am>-1)
	{
		var kf=kuerzen(A,am,B,bm);
		if(kf!="1")
		{
			T+="Dieser Restquotient kann mit "+kf+" gekürzt werden.\n\n"; 
			am=getMaxKoeff(A);
			bm=getMaxKoeff(B);
			ta=PStr("x",A);
			//alert(kf);
		}		
	}
	if((am==0)&&(A[0].n!=1))
	{
		for(i=0;i<B.length;i++){B[i].z*=A[0].n;B[i].kuerzen();}
		A[0].n=1;ta=A[0].z;
	}
	if((am==0)&&(B[bm].z<0))
	{
		A[0].z=-A[0].z;ta=PStr("x",A);
		for(i=0;i<=bm;i++)B[i].z=-B[i].z;
	}
	var vz="+";	
	if(ta!="0")
	{
		if(A[am].z<0){for(i=0;i<=am;i++)A[i].z=-A[i].z;ta=PStr("x",A);vz="-";}
		if(B[bm].z<0){for(i=0;i<=bm;i++)B[i].z=-B[i].z;tb=PStr("x",B);vz=(vz=="+")?"-":"+";}
	}
	tb=PStr("x",B);
	if((am>0)||(A[0].n!=1))ta="("+ta+")";
	if(bm>0)tb="("+tb+")";
	if(bm==0)if(B[0].z<0)tb="("+tb+")";
	t=PStr("x",Q); 
	if(ta!="0")	t=t+" "+vz+" "+ta+"/"+tb;
	t=t.replace(/\+ -/,"- ").replace(/\(x\)/g,"x");
//	t=t.replace(/\^2 /g,"² ").replace(/\^3 /g,"³ ");
	if(t.substr(0,4)=="0 + ")t=t.substring(4,t.length);
	if(t.substr(0,4)=="0 - ")t="-"+t.substring(4,t.length);
	T+="Es ergibt sich somit das folgende Ergebnis der Polynomdivision:\n\n"+t+"\n\n";
	T=T.replace(/ 1x/g," x").replace(/-1x/g,"-x").replace(/·1x/g,"·x");
//	T=T.replace(/\^2 /g,"² ").replace(/\^3 /g,"³ ");
	if((VV.length==1)&&(VV[0]!="x"))
	{
		T=T.replace(/x/g,VV[0]);
		t=t.replace(/x/g,VV[0]);
		document.f.p0.value=document.f.p0.value.replace(/x/g,VV[0]);
		document.f.p1.value=document.f.p1.value.replace(/x/g,VV[0]);
	}
	document.f.Erkl.value=(T);
	document.f.vars.value=VV[0];
	status="";

	document.f.Erkltab.value=polydivtab(atab,p1,PStr("x",Q),mtab,VV[0]);

	return t;
}


//p: Polynom (String), v: Variable (String), K: Array mit RationalenZahlen für Koeffizienten
function parsePolynom(p,v,K)
{
	var PPP=p;
	p=p.replace(/—/g,"-").replace(/–/g,"-");
	p=(" "+p+" ").replace(/\+/g," +").replace(/-/g," -").replace(/x\^0 /g," ");
	p=" "+p.replace(/ /g,"").replace(/,/g,".").replace(/²/g,"2").replace(/³/g,"3").replace(/\^/g,"");
	p=p.replace(/·/g,"").replace(/\*/g,"").replace(/•/g,"").replace(/,/g,".");
	p=p.replace(/xxxxxxxxxx/g,"x^10").replace(/xxxxxxxxx/g,"x^9");
	p=p.replace(/xxxxxxxx/g,"x^8").replace(/xxxxxxx/g,"x^7");
	p=p.replace(/xxxxxx/g,"x^6").replace(/xxxxx/g,"x^5");
	p=p.replace(/xxxx/g,"x^4").replace(/xxx/g,"x^3").replace(/xx/g,"x^2");
	p=p.replace(/x\^/g,"x");
	//p=p.replace(/x^0/g,"*1");
	var pp=p.replace(/\d/g,"¶").replace(/,/g,"¶").replace(/\./g,"¶").replace(/p/g,"¶").replace(/_/g,"¶");
	var i,je,jk,k,e;
	var b=new RationaleZahl(0,1);
	for(i=0;i<K.length;i++)K[i].set(0,1);
	for(i=0;i<p.length;i++)
	{
		if(pp.charAt(i)!=v)continue;
		for(jk=i-1;jk>=0;jk--) {if(pp.charAt(jk)!="¶")break;}
		k=Number(p.substring(jk,i)); 
		if(jk==i-1)	k=(p.charAt(jk)=="-")?-1:1;
		for(je=i+1;je<pp.length;je++) {if(pp.charAt(je)!="¶")break;}
		e=Number(p.substring(i+1,je));
		if((je==i+1))e=1; 
		if(p.charAt(jk)=="/")
		{
			for(jk=jk-1;jk>=0;jk--) {if(pp.charAt(jk)!="¶")break;}
			var B=p.substring(jk,i).split("/");
			b.set(B[0],B[1]);
		}
		else if((k!=Math.floor(k))||(p.substring(jk,i).indexOf("p")>-1))
		{
			var B=getBruchFromDez(p.substring(jk,i)).split("/");
			b.set(B[0],B[1]);
		}
		else
		{
			b.set(k,1);
		}
		if(e>K.length-1)for(var ii=K.length;ii<=e;ii++)K[ii]=new RationaleZahl(0,1);
		K[e].add(b);
//		alert("parse: "+PPP+"\n"+K[e].str()+"·"+v+"^"+e);
		for(i=jk;i<je;i++)p=p.substr(0,i)+" "+p.substring(i+1,p.length);
	}
	pp=p.replace(/ /g,"");
	if(pp.charAt(0)=="+")pp=pp.substr(1,pp.length);
	while((pp.length>0)&&(pp.substr(pp.length-1,1).match(/\d/)==null))pp=pp.substr(0,pp.length-1);
	B=calcbruchterm(pp).split("/");
	if(B[0]=="Fehler")B[0]=0;
	if(B.length==2)b.set(B[0],B[1]); else {b.z=B[0];b.n=1;}	
	K[0].add(b);
//	alert("parse: "+PPP+"\n"+K[0].str());
	
}

function PStr(v,k)
// Erzeugt einen Polynomstring über die Variable v mit den Koeffizienten k[]
{
	var t="",g=k.length-1;kk=new Array(g+1);
	kk[0]=k[0].str();
	for(i=1;i<=g;i++) kk[i]=(Math.abs(k[i].z)==k[i].n)?((k[i].z==k[i].n)?"":"-"):k[i].str();
	for(i=g;i>1;i--) if(k[i].z!=0)t+="+"+kk[i]+v+"^"+i;
	if((k[1].z!=0)&&(g>0))t+="+"+kk[1]+v; if(k[0].z!=0)t+="+"+kk[0];
	t=t.replace(/\+\-/g,"-").replace(/\+/g," + ").replace(/\-/g," - ").replace(/\+/g," + ").replace(/\s\s/g," ");
	if(t.substr(0,3)==" - ")t="-"+t.substring(3,t.length);
	if(t.substr(0,2)==" +")t=t.substring(2,t.length);
	while(t.substr(0,1)==" ")t=t.substring(1,t.length);
	if(t=="")t="0";
	return t;
}

function zufallspolynome(p,kb)
{
	var o=(8==9);
	if(kb==null)kb=1;
	if(p<0){p=-p;o=true;}
	if(p==null)p=0.5;
	var i,j;
	for(i=0;i<Q.length;i++){Q[i].set(0,1);B[i].set(0,1);A[i].set(0,1);C[i].set(0,1);}
	status="Erzeuge Zufallspolynome";
	var b=new RationaleZahl(0,1);
	var g0=rnd(1,5);
	do{Zufallsterm(g0,5,5,0.4,0.05*kb,B);j=0;for(i=0;i<B.length;i++)if(B[i].z>0)j++;}while(j<2);
	var g1=rnd(1,5);
	do{Zufallsterm(g1,3,6,0.5,0.1*kb,C);j=0;for(i=0;i<C.length;i++)if(C[i].z>0)j++;}while(j<2);
	for(i=0;i<=g0;i++)for(j=0;j<=g1;j++)	
	{
		b.set(B[i].z,B[i].n);
		b.mult(C[j]);
		A[i+j].add(b);
	}
	if(Math.random()<p)
	{
		var g=rnd(0,g0);
		Zufallsterm(g,5,4,0.6,0.05*kb,Q);
		for(i=0;i<=g;i++)A[i].add(Q[i]);
	}
	if(o)
	{
		return new Array(PStr("x",A),PStr("x",B),PStr("x",C),PStr("x",Q));
	}
	document.f.p0.value=PStr("x",A);
	document.f.p1.value=PStr("x",B);
	document.f.p2.value=polydiv(document.f.p0.value,document.f.p1.value);
	status="";
}

function Zufallsterm(g,max,n,p0,pb,K)
// g: Grad, max: maximaler Koeffizient, n: maximaler Nenner
// p0: Wahrscheinlichkeit für K[i]=0, K: Koeffizienten
// pb: Wahrscheinlichkeit für Nenner!=1
{
	for(var i=0;i<=g;i++)
	{
		nn=(Math.random()<pb)?rnd(2,n):1;
		if((Math.random()<p0)&&(i<g)) K[i].set(0,1);
		else
		{
			var N=nn;//rnd(1,nn);
			K[i].set(rnd(-max*N,max*N),N);
			K[i].kuerzen(0);
		}
	}
}

function rnd(n0,n1)
{
	var n;
	{n=Math.floor(Math.random()*(n1-n0)+n0);}
	return n;
}

function kuerzen(A,am,B,bm)
{
	var i=0,s="";
	if((A[am].z<0)&&(B[bm].z)<0)
	{
		for(i=0;i<=am;i++)A[i].z=-A[i].z;
		for(i=0;i<=bm;i++)B[i].z=-B[i].z;
		s="-";
	}
	var gz=Math.abs(A[am].z),gn=A[am].n,i=0,a0=-1;b0=-1;
	for(i=0;i<am;i++)
	{
		if(A[i].z!=0)
		{
			gz=ggT(gz,Math.abs(A[i].z));
			gn=ggT(gn,A[i].n);
		}
		if((gn==1)&&(gz==1))break;
	}
	for(i=0;i<=bm;i++)
	{
		if(B[i].z!=0)
		{
			gz=ggT(gz,Math.abs(B[i].z));
			gn=ggT(gn,B[i].n);
		}
		if((gn==1)&&(gz==1))break;
	}
	for(i=0;i<=am;i++){A[i].z/=gz;A[i].n/=gn;if((a0==-1)&&(A[i].z!=0))a0=i;}
	for(i=0;i<=bm;i++){B[i].z/=gz;B[i].n/=gn;if((b0==-1)&&(B[i].z!=0))b0=i;}
	if(s=="-")gz=-gz;
	var k= (gn!=1)?gz+"/"+gn:gz;
	var min=(b0<a0)?b0:a0; 
	if(min>0)
	{
		for(i=0;i<=am-min;i++){A[i].z=A[i+min].z;A[i].n=A[i+min].n;}
		for(i=am-min+1;i<=am;i++)A[i].set(0,1);
		for(i=0;i<=bm-min;i++){B[i].z=B[i+min].z;B[i].n=B[i+min].n;}
		for(i=bm-min+1;i<=bm;i++)B[i].set(0,1);
	}
	am=getMaxKoeff(A);bm=getMaxKoeff(B);
	if((A[am].z<0)&&(B[bm].z<0))
	{
		for(i=0;i<=am;i++)A[i].z=-A[i].z;for(i=0;i<=bm;i++)B[i].z=-B[i].z;
		k=-k;
	}
	var v=(min==1)?"x":((min>1)?"x^"+min:"");
	if((k=="1")&&(v!=""))return v;
	if((k=="-1")&&(v!=""))return "-"+v;
	return k+v;
}