var MultErg=new Array(/\dx/,/\d\(/,/\)\(/,/x\(/,/\)x/,/pi\(/,/e_\(/,/\dpi/,/\de_/);
var grad_rad=Grad_rad=1;
trigo=1;
var IncT="";
var versuch=0;
var blinker=new Image();
blinker.src="../bilder/blink_on.gif";
var komplexePolynomdivision=(1==0);
var useApplet=(1==0);

function calcKoeffs2(x1,y1,x2,y2,x3,y3,k)
{
k[2]=(x3*(y2-y1)+x2*(y1-y3)+x1*(y3-y2))/((x1-x2)*(x3-x1)*(x3-x2));
k[1]=(x3*x3*(y2-y1)+x2*x2*(y1-y3)+x1*x1*(y3-y2))/((x2-x1)*(x3-x1)*(x3-x2));
k[0]=(x3*x3*(x2*y1-x1*y2)+x3*(x1*x1*y2-x2*x2*y1)+x1*x2*y3*(x2-x1))/((x2-x1)*(x3-x1)*(x3-x2));
}

function solvePolynom2()
{
	var Startzeit0=new Date();
	var prog="Javascript";
	useApplet=false;
	if(navigator.javaEnabled()){if(document.f.useapplet!=null)useApplet=document.f.useapplet.checked;}
	document.images[0].src=blinker.src;
	document.images[1].src=blinker.src;
	document.images[2].src=blinker.src;
	var nvk=1e100,dvk=0;
	switch(document.f2.nvk.selectedIndex)
	{
	case 0:nvk=1e100;break;case 1:nvk=100;break;case 2:nvk=200;break;case 3:nvk=1000;break;
	case 4:dvk=10;break;case 5:dvk=30;break;case 6:dvk=60;break;
	case 7:dvk=120;break;case 8:dvk=300;break;case 9:dvk=600;break;
	default:
	}
	var F=document.f;
	komplexePolynomdivision=false;//F.usekpd.checked;
	var maxgrad=Number(F.maxgrad.options[F.maxgrad.selectedIndex].text);
	t=F.inp.value.toLowerCase();
	var IncTT=t,TT="",TPD="",KTPD="",klammer=t.indexOf("(");
	t=t.replace(/,/g,".").replace(/²/g,"^2").replace(/³/g,"^3");
	t=t.replace(/·/g,"*").replace(/ +/g,"");
	while(t.indexOf("xx")>-1){t=t.replace(/xx/,"x*x");}
	var i,j,T="",k=new Array(20),kk=new Array(20),g=2,gg,N="";
	for(j=0;j<MultErg.length;j++)
		do{i=t.search(MultErg[j]);if(i==-1)break;t=t.substr(0,i+1)+"*"+t.substring(i+1,t.length);}while(true);
	var spt=new Array(1);spt[0]=t;
	if(t.indexOf("=")>-1){spt=t.split("=");t=spt[0]+"-("+spt[1]+")";}
	N=extrahiereNenner(t);
	if(F.brueche.checked)
		if(N!="")t="("+t+")*"+(N);	
		t=translate(t);
	if((klammer==-1)&&(N==""))
	{
		status="Vereinfache Polynom";
		clear(k);
		parsePolynom(spt[0],"x",k);
		
		if(spt.length==2)
		{
			var kk=new Array(20);
			parsePolynom(spt[1],"x",kk);
			//alert(kk);
			for(i=0;i<Math.max(k.length,kk.length);i++)
			{
				if(i>=k.length)k[i]=0;
				if(i>=kk.length)kk[i]=0;
				k[i]-=kk[i];
			}
		}
		g=k.length-1;gg=g;
		//klammer=Test(k,g,t,true)?-1:0;
	}
	if((klammer>-1)||(N!=""))
	{
		status="Quadratisches Polynom?";
		//if(N!="")t="("+t+")*"+translate(N);
		var x1=-Math.random()*20,x2=Math.random()*10-5,x3=Math.random()*20;
		var y1=eval(t.replace(/X/g,"x1")+";");//T+="f("+(-Math.PI*Math.E)+")="+y1+"\n";
		var y2=eval(t.replace(/X/g,"x2")+";");//T+="f("+Math.PI+")="+y2+"\n";
		var y3=eval(t.replace(/X/g,"x3")+";");//T+="f("+(Math.PI*Math.PI)+")="+y3+"\n";
		clear(k);
		calcKoeffs2(x1,y1,x2,y2,x3,y3,k);gg=2; 
		if(!Test(k,g,t,false))
		{
			versuch++;
/*			status="Erzeuge Regressionsmatrix";
			var X=new Array(maxgrad*2+1);Y=new Array(maxgrad*2+1);XP=new Array();XY=new Array();
			for(i=0;i<=maxgrad*2+1;i++){XP[i]=0;XY[i]=0;}
			for(i=0;i<=maxgrad*50;i++)
			{
				do{
					X[i]=(Math.random()*4-2);
					Y[i]=eval(t.replace(/X/g,"("+X[i]+")"));
				}while((isNaN(Y[i]))||(Math.abs(Y[i])>1000));
				var x=1;
				for(j=0;j<=maxgrad*2+1;j++){XP[j]+=x;XY[j]+=Y[i]*x;x*=X[i];}
			}
//alert(XP.join("  ")+"\n\n"+XY.join("  ")+"\n\n"+Y.join("  "));
*/
			for(g=3;g<=maxgrad;g++)
			{
				status="Erzeuge Gleichungssystem, Grad "+g;
				var m=new Array((g+1)*(g+2));
				clear(m);
				for(i=0;i<m.length;i++)m[i]=0;
				x1=-g/2;
				for(i=0;i<g+1;i++)
				{
					x1+=Math.round(Math.random()*20)/10;
					m[(g+2)*i+g+1]=eval(t.replace(/X/g,"x1"));
					while(Math.abs(m[(g+2)*i+g+1])==(1/0))
					{
						x1+=Math.round(Math.random()*20)/10;
						m[(g+2)*i+g+1]=eval(t.replace(/X/g,"x1"));
					}
					m[(g+2)*i]=1;
					for(j=1;j<g+1;j++)m[(g+2)*i+j]=m[(g+2)*i+j-1]*x1;
				}

/*				i=0; 
				for(var zm=0;zm<g+1;zm++)
				{
					for(var sm=0;sm<g+1;sm++)m[i++]=XP[zm+sm];
					m[i++]=XY[zm];
				}
*/
				status="  Löse  Gleichungssystem, Grad "+g;
				clear(k);
				
				GLSL(m,k,g+1);
				//if(g==18)alert("Grad: "+g+"\n\n"+m.join("  ")+"\n\n"+k.join("  "));
				// document.f.normalform.value= PStr("x",k,g);return;
				gg=g;
				if(Test(k,g,t,true))break;
			}
			if(g>=maxgrad)
			{
				status="Teste Lösungsvektor";
				if(!Test(k,gg,t,true))
				{
					document.f.normalform.value="Kein Polynom vom Grad <="+maxgrad+" erkannt";
					status="";
					if(versuch<5)solvePolynom();else versuch=0;
					blinkoff();
					return;
				}
			}
		}
	}
	var Startzeit=new Date();
	F.ngl.value=0;
	var parsedauer=("Das Übersetzen der Eingabe dauerte "+(Math.round((Startzeit.getTime()-Startzeit0.getTime())/100)/10)).replace(/\./,",").replace(/ ,/," 0,")+"s ";
	g=gg;
	status="";versuch=0;
	var k_=new Array(k.length),kk_=new Array(k.length);
	for(i=0;i<=g;i++)
	{
		if(Math.abs(k[i]-Math.round(k[i]))<1e-5)k[i]=Math.round(k[i]);
		k_[i]=k[i];
	}
	//alert(k);
	while((k[g]==0)&&(g>2))g--;
	if((g<3)&&(k[0]==0)&&(k[1]==0)&&(k[2]==0)){alert("Fehler");return;}
	if(k[g]<0)for(i=0;i<=g;i++)k[i]=-k[i];
	T+=PStr("x",k,g)+" = 0"; 
	if(T.indexOf("NaN")>-1){F.normalform.value="Kein Polynom vom Grad <="+maxgrad+" erkannt";blinkoff();return;}
	document.f.normalform.value=T;
	var K=new Array(g+1);
	Ableitung(k,kk,g);
	Ableitung(k_,kk_,g);
	for(i=0;i<=g;i++)K[i]=(" "+String(k[i])).replace(/\./,",").replace(/-,/,"-0,").replace(/ ,/,"0,").replace(/ /,"");
	if(g<5)
	{
		if(g!=4){F.p4a.value="";F.p4b.value="";F.p4c.value="";F.p4d.value="";F.p4e.value="";F.x44.value="";F.x43.value="";F.x42.value="";F.x41.value="";}
		if(g!=3){F.p3a.value="";F.p3b.value="";F.p3c.value="";F.p3d.value="";F.x33.value="";F.x32.value="";F.x31.value="";}
		if(g>2){F.p2a.value="";F.p2b.value="";F.p2c.value="";F.x22.value="";F.x21.value="";}
	}
	gg=g;
	switch(g)
	{
	case 2:F.p2a.value=(k[2]!=0)?K[2]:"";F.p2b.value=(k[1]!=0)?K[1]:"";F.p2c.value=K[0];solvePolynom(2);break;
	case 3:F.p3a.value=K[3];F.p3b.value=K[2];F.p3c.value=K[1];F.p3d.value=K[0];solvePolynom(3);break;
	case 4:F.p4a.value=K[4];F.p4b.value=K[3];F.p4c.value=K[2];F.p4d.value=K[1];F.p4e.value=K[0];solvePolynom(4);break;
	default:
	};
	if(F.lapr.checked)
	{
		var n=0,nreell,xxr=new Array(g),xxi=new Array(g);
	if(!useApplet)
	{
		status="Nullstellensuche: Ausprobieren, "+Math.floor(i+50)+"%, bislang gefunden: "+n+"/"+gg;
		while(k[0]==0)
		{
			xxr[n]=0;xxi[n]=0;
			for(j=0;j<g;j++)k[j]=k[j+1];
			k[g]=0;
			TPD+="Nullstelle x=0   (Ausklammern von x)\n  ——>  reduziertes Polynom:  "+PStr("x",k,g)+"\n\n";
			g--;
			n++;F.ngl.value=n;
			Ableitung(k,kk,g);
			if(g==0)break;
			if(g==1){xxr[n]=-k[0]/k[1];xxi[n++]=0;g=0;break;}
		}
		for(i=-50;(i<=50) && (n<gg);i+=0.25)
		{
			var y;
			while(Math.abs(y=HornerR(k,g,i))<1e-10)
			{
				xxr[n]=i;xxi[n]=0;
				if(polydivR(k,g,i))TPD+="Nullstelle x="+i+"   (gefunden durch Ausprobieren)\n  ——>  reduziertes Polynom:  "+PStr("x",k,g)+"\n\n";
				while((k[g]==0)&&(g>1))g--;//alert("(0)\n"+i+"\n"+PStr("x",k,g));
				n++;F.ngl.value=n;
				Ableitung(k,kk,g);
				if(g==0)break;
				if(g==1){xxr[n]=-k[0]/k[1];xxi[n++]=0;g=0;break;}
			}
		}
		i=0;
		while((i<gg)&&(n<gg))
		{
			i++;
			status="Nullstellensuche: Newton reell, "+Math.floor(i*100/gg/2)+"%, bislang gefunden: "+n+"/"+gg;
			var xr=(Math.random()*Math.random()*20.0-5)*i/5;
			xi=0;
			var y=0;
			if((y=NewtonR_(xr,k,kk,gg,200))!=false)
			{
				if(Math.abs(HornerR(k_,gg,y))>1e-10)continue;
				for(j=0;j<n;j++)if(runden(xxr[j])==runden(y))break;
				if(j<n)continue;
				xxr[n]=y;xxi[n]=0;
				if(polydivR(k,g,y))TPD+="Nullstelle x="+y+"   (gefunden durch reellen Newton-Algorithmus)\n  ——>  reduziertes Polynom:  "+PStr("x",k,g)+"\n\n";
				
				while((k[g]==0)&&(g>1))g--;//alert("(1)\n"+y+"\n"+PStr("x",k,g));
				n++;F.ngl.value=n;Ableitung(k,kk,g);
				if(g==0)break;
				if(g==2)
				{	
					k[0]/=k[2];k[1]/=k[2];k[2]=1;
					var D=k[1]*k[1]/4-k[0];
					var x1,x2,xi,xr,Y=new Array(0,0);
					if(D>=0)
					{
						x1=-k[1]/2-Math.sqrt(D);
						y=NewtonR_(x1,k_,kk_,gg,100);
						if(Math.abs(HornerR(k_,gg,y))<1e-8)
						{
							xxi[n]=0;xxr[n++]=y;F.ngl.value=n;
							if(polydivR(k,g,y))TPD+="Nullstelle x="+y+"   (gefunden durch reellen Newton-Algorithmus)\n  ——>  reduziertes Polynom:  "+PStr("x",k,g)+"\n\n";
						}
						x2=-k[1]/2+Math.sqrt(D);
						y=NewtonR_(x2,k_,kk_,gg,100);
						if(Math.abs(HornerR(k_,gg,y))<1e-8)
						{
							xxi[n]=0;xxr[n++]=y;F.ngl.value=n;
							if(polydivR(k,g,y))TPD+="Nullstelle x="+y+"   (gefunden durch reellen Newton-Algorithmus)\n  ——>  reduziertes Polynom:  "+PStr("x",k,g)+"\n\n";
						}
						Ableitung(k,kk,g);
					}
					else
					{
						xr=-k[1]/2;
						xi=-Math.sqrt(-D);
						var erg=Newton_(xr,xi,k_,kk_,gg,100,Y);
						if(true)
						{	
							xxr[n]=Y[0];xxi[n++]=Y[1];F.ngl.value=n;
							xxr[n]=Y[0];xxi[n++]=-Y[1];F.ngl.value=n;
						}
					}
				}
				if(g==1)
				{
					y=-k[0]/k[1];xxi[n]=0;g=0;
					y=NewtonR_(y,k_,kk_,gg,100);
					if(Math.abs(HornerR(k_,gg,y))<1e-8){xxr[n++]=y;F.ngl.value=n;break;}
				}
			} 
		}
		var tryconj=(1==0),jetzt=new Date();
		nreell=n; 
		var millis=jetzt.getTime(), dvkstop=millis+dvk*1000;
		var kr=new Array(g+1),ki=new Array(g+1);
		for(i=0;i<=g;i++){kr[i]=k[i];ki[i]=0;}
		i=0;
		while((i<nvk+gg)&&(n<gg))
		{
			i++;
			var proz=Math.floor(i*100/(nvk+g));
			if(nvk>10000)proz=Math.floor(100*(n-nreell)/(gg-nreell));
			if(dvk>0){if((jetzt=new Date()).getTime()>dvkstop)break;proz=Math.floor(100*(1-(dvkstop-jetzt.getTime())/dvk/1000));}
			var xr,yr;
			if(!tryconj)
			{
				if(i<100)
				{
					xr=(Math.random()*20.0-10)*i/10;
					xi=(Math.random()*20.0-10)*i/10;
					if(Math.random()>.8){xr*=100;xi*=100;}
				}
				else
				{
					xr=(Math.random()*Math.random()*Math.random()*Math.random()*1000.0);
					xi=(Math.random()*Math.random()*Math.random()*Math.random()*1000.0);
					if(Math.random()>.5)xr=-xr;
					if(Math.random()>.5)xi=-xi;
				}
				
				//var o=i*Math.PI/gg;
				//xr=Math.cos(o)*i/10;
				//xr=Math.sin(o)*i/10;
			}
			else
			{
				xi=-xi;
				i--;
			}
			if(i<gg){xr=-((gg%2)-.5)*2*Math.cos(i*2*Math.PI/gg)/k_[gg];xi=Math.sin(i*2*Math.PI/gg)/k_[gg];}

			if(komplexePolynomdivision)
			{
				var y=new Array(0,0),erg=false;
				if((Math.random()>.0)&&(i>gg))
					erg=NewtonK_(xr,xi,kr,ki,g,100,y);
				else erg=Newton_(xr,xi,k_,kk_,gg,100,y);
				
				status="Nullstellensuche: Newton k-komplex "+Math.floor(proz)+"%, bislang gefunden: "+n+"/"+gg + "  ("+nreell+" reelle und "+(n-nreell)+" komplexe)";
				if(erg)
				{
					if(isNaN(y[0]))continue;
					if(alert(DNull_(y[0],y[1],k_,gg))>1e-5)continue;
					alert(DNullK_(y[0],y[1],kr,ki,g));
					for(j=0;j<n;j++)if((runden(xxr[j])==runden(y[0]))&&(runden(xxi[j])==runden(y[1])))break;
					if(j<n)continue;
					xxr[n]=y[0];xxi[n]=y[1];//alert("(2)\n"+L(y[0],y[1])+"\n"+PStr("x",k,g));
					//while((k[g]==0)&&(g>1))g--;//alert(PStr("x",k,g));
					n++;
					for(j=0;j<n;j++)if((runden(xxr[j])==runden(y[0]))&&(-runden(xxi[j])==runden(y[1])))break;
					tryconj=(j==n);
					alert("Komplexe Nullstelle "+L(y[0],y[1])+"\n"+DNullK_(y[0],y[1],kr,ki,g));
					if(polydivK(kr,ki,g,y[0],y[1]))g--;
					KTPD+="Komplexe Nullstelle "+L(y[0],y[1])+"):\n";
					for(i=g;i>1;i--)TPD+="("+L(kr[i],ki[i])+")x^"+i+" + ";
					KTPD+="("+L(kr[1],ki[1])+"x + ("+L(kr[0],ki[0])+"\n\n";
				}
				

			}
			else
			{
				var y=new Array(0,0),erg=false;
				if((Math.random()>.5)&&(i>gg))erg=Newton_(xr,xi,k,kk,g,100,y);else erg=Newton_(xr,xi,k_,kk_,gg,100,y);
				//if(i<gg)alert(L(y[0],y[1])+"\n"+DNull_(y[0],y[1],k_,gg));
				
				status="Nullstellensuche: Newton komplex "+Math.floor(proz)+"%, bislang gefunden: "+n+"/"+gg + "  ("+nreell+" reelle und "+(n-nreell)+" komplexe)";
				if(erg)
				{
					if(isNaN(y[0]))continue;
					if(DNull_(y[0],y[1],k_,gg)>1e-5)continue;
					for(j=0;j<n;j++)if((runden(xxr[j])==runden(y[0]))&&(runden(xxi[j])==runden(y[1])))break;
					if(j<n)continue;
					xxr[n]=y[0];xxi[n]=y[1];//alert("(2)\n"+L(y[0],y[1])+"\n"+PStr("x",k,g));
					while((k[g]==0)&&(g>1))g--;//alert(PStr("x",k,g));
					n++;F.ngl.value=n;
					for(j=0;j<n;j++)if((runden(xxr[j])==runden(y[0]))&&(-runden(xxi[j])==runden(y[1])))break;
					tryconj=(j==n);
					if(tryconj)
					{
						if(polydivRK(k,g,y[0],y[1]))
						{
							xxr[n]=y[0];xxi[n++]=-y[1];F.ngl.value=n;
							KTPD+="Konjugierte komplexe Nullstellen  "+L(y[0],-Math.abs(y[1])).replace(/ - /," ± ").replace(/ \+ /," ± ")+"\n";
							KTPD+="  ——>  reduziertes Polynom:  "+PStr("x",k,g)+"\n\n";
							Ableitung(k,kk,g);
						}
						tryconj=false;
					}
					while((k[g]==0)&&(g>1))g--;//alert(PStr("x",k,g));
				}
			}
			//if(g==1){xxr[n]=-k[0]/k[1];xxi[n++]=0;g=0;break;}
		}
		}
		else
		{
			var NSr=new Array(),NSi=new Array();
			status="Nullstellensuche per Applet";
			prog="Java-Applet";
			var ans=String(document.applet.calcNullstellen(k_.join(" ")," , ","\n"));
			//alert(ans);
			var ns=ans.split("\n");
			n=ns.length;
			var kkk=new Array();
			for(i=0;i<=g;i++)kkk[i]=k[i];
			TPD="";
			for(i=0;i<ns.length;i++)
			{
				nss=ns[i].split(" , ");
				xxr[i]=Number(nss[0]);xxi[i]=Number(nss[1]);
			}
			for(i=0;i<ns.length;i++)
			{
				if(xxi[i]==0)
				{
					polydivR(kkk,g,xxr[i]);
					while((kkk[g]=0)&&(g>0))g--;
					TPD+="Nullstelle  x = "+L(xxr[i],xxi[i])+"\n  ——>  reduziertes Polynom:  "+PStr("x",kkk,g)+"\n\n";
				}
			}
			KTPD="";
			for(i=0;i<ns.length;i++)
			{
				if(xxi[i]!=0)
				{
					if(polydivRK(kkk,g,xxr[i],xxi[i]))
					{
						while((kkk[g]=0)&&(g>0))g--;
						KTPD+=("konjugierte komplexe Nullstellen  x = "+L(xxr[i],xxi[i])+"\n  ——>  reduziertes Polynom:  "+PStr("x",kkk,g)+"\n\n").replace(/ - /," ± ").replace(/ \+ /," ± ");
					}
				}
			}
			status=n+" Nullstellen gefunden";
		}
		if(n>0)
		{
			var Y=new Array(0,0),x_=0;//alert(k_+"\n"+gg+"\n"+xxr);
			F.ngl.value=n;
			for(i=0;i<n;i++)
			{
				if(xxi[i]!=0)
					if(Newton_(xxr[i],xxi[i],k_,kk_,gg,200,Y))
					{
						if(DNull_(Y[0],Y[1],k_,gg)<DNull_(xxr[i],xxi[i],k_,gg)){xxr[i]=Y[0];xxi[i]=Y[1];}
					}
				else
					{
						x_=NewtonR_(xxr[i],k_,kk_,gg,500);
						if(Math.abs(HornerR(k_,gg,x_))<Math.abs(HornerR(k_,gg,xxr[i])))xxr[i]=x_;
					}
			}
			status="Sortieren";
			sortiere(xxr,xxi,n);
			var NN=translate(N);
			for(i=0;i<n-1;i++)
			{
				if((Math.abs(xxr[i]-xxr[i+1])<1e-12)&&(xxi[i]>xxi[i+1]))
				{
					var sw=xxr[i];xxr[i]=xxr[i+1];xxr[i+1]=sw;
					sw=xxi[i];xxi[i]=xxi[i+1];xxi[i+1]=sw;
				}
			}
			for(i=0;i<n;i++)
			{
				if(N!="")
				{
					var ny,Fehler="   Folgende Nullstelle gehört nicht zur Definitionsmenge, weil an dieser Stelle \n   ein Nenner Null wird *)";
					ny=(xxi[i]==0)?eval(NN.replace(/X/g,"("+xxr[i]+")")):1;
					if(Math.abs(ny)<1e-14)TT+=Fehler+"\n";
				}
				TT+=((i<9)?" ":"")+"  x"+(i+1)+" = "+((xxr[i]>=0)?" ":"")+L(xxr[i],xxi[i])+"\n";//  L(Math.round(xxr[i]*1.0e+12)/1.0e+12,Math.round(xxi[i]*1.0e+12)/1.0e+12)+"\n    "+(i+1)+"\n\n";
			}
			var mz=(gg-n==1)?"":"n";
			if(n<gg)TT+="\n"+(gg-n)+" Nullstelle"+mz+" konnte"+mz+" nicht gefunden werden.\n\n";
			if(N!="")TT+="\n\n*) Die Definitionsmenge wird eingeschränkt durch die Lösungen des Polynoms \n   (Produkt der Nenner): "+N;
			TT+="\n\n\nProbe mit dem Standardpolynom - bei genauen Nullstellen muß P(x)=0 sein:\n\n";
			for(i=0;i<n;i++)
			{
				HornerK(k_,gg,xxr[i],xxi[i],Y);
				var ny,Fehler="   Folgende Nullstelle gehört nicht zur Definitionsmenge, weil an dieser Stelle \n   ein Nenner Null wird:";
				if(N!="")
				{
					ny=(xxi[i]==0)?eval(NN.replace(/X/g,"("+xxr[i]+")")):1;
					if(Math.abs(ny)<1e-14)TT+=Fehler+"\n";
				}
				TT+="   P(x"+(i+1)+") = "+L(Y[0],Y[1])+"\n";
			}	
			TT+="\n\nProbe der reellen Nullstellen mit der eingegebenen Gleichung\n\n";
			for(i=0;i<n;i++)
			{
				var Fehler="Fehler: Wert gehört möglicherweise nicht zur Definitionsmenge (siehe oben).";
				if(xxi[i]==0)
				TT+=( "   G( "+(xxr[i])+") = "+eval(t.replace(/X/g,"("+xxr[i]+")"))+"\n").replace(/\./g,",").replace(/ ,/g," 0,").replace(/-,/g,"-0,").replace(/NaN/g,Fehler).replace(/\( /,"(");
			}	
			TPD=TPD.replace(/\./g,",").replace(/-,/g,"-0,").replace(/ ,/g," 0,").replace(/=,/g,"=0,");
			if(TPD!="")TPD="Polynomdivisionen bei reellen Nullstellen:\n\n"+TPD;
			if(KTPD!="")KTPD="Polynomdivisionen bei konjugierten komplexen Nullstellenpaaren:\n\n"+KTPD.replace(/- -/g,"+ ");
			T=T.replace(/²/g,"^2");
			T="Durch das Newton-Verfahren gefundene Lösungen der Gleichung\n   "+T+"\n\n\n"+TT+"\n\n\n";;
			T+=TPD+"\n\n"+KTPD+"\n\n\n";
			T+=parsedauer+("und die Nullstellensuche per "+prog+" "+(Math.round(((new Date()).getTime()-Startzeit.getTime())/100)/10)).replace(/\./,",").replace(/ ,/," 0,")+"s.\n\n";
			if((document.applet!=null)&&(!useApplet)&&(gg<20)&&(document.applet.calcNullstellen!=null))
			{
				var NSr=new Array(),NSi=new Array();
				var ans=String(document.applet.calcNullstellen(k_.join(" "),",",";"));
				var ns=ans.split(";");
				T+="\nNullstellen, gefunden von Applet:\n\n";
				for(i=0;i<ns.length;i++){var nss=ns[i].split(",");NSr[i]=Number(nss[0]);NSi[i]=Number(nss[1]);}
				sortiere(NSr,NSi,ns.length);
				for(i=0;i<ns.length;i++)
				{
					if((Math.abs(NSr[i]-NSr[i+1])<1e-12)&&(NSi[i]>NSi[i+1]))
					{
						var sw=NSr[i];NSr[i]=NSr[i+1];NSr[i+1]=sw;
						sw=NSi[i];NSi[i]=NSi[i+1];NSi[i+1]=sw;
					}
				}
				for(i=0;i<ns.length;i++)
				{
					T+="   x"+(i+1)+" = "+L(NSr[i],NSi[i])+"\n";
				}
				T+="\n\n\n";
			}
			T+="Javascript und Applet: © Arndt Brünner\n";
			T="                                                                                 Modus: "+prog+"\n"+T;
			F.text.value=T+"\n\n";
		}
		else
		{
			F.text.value="Durch das Newton-Verfahren wurden keine Lösungen \nder Gleichung  "+T+"  gefunden.\n\n";
		}
	}
	IncT="Die Eingabe "+IncTT+" wurde in die Standardform gebracht:\n"+T;
	status="fertig - "+((n==gg)?"alle ":n+"/")+gg +" Nullstellen gefunden";
	blinkoff();
}

function PStr(v,k,g)
// Erzeugt einen Polynomstring über die Variable v mit den Koeffizienten k[]
{
	var t="",kk=new Array(g+1);
	kk[0]=String(k[0]);
	for(i=1;i<=g;i++) kk[i]=((k[i]==1)||(k[i]==-1))?((k[i]==1)?"":"-"):String(k[i]);
	for(i=0;i<=g;i++) {kk[i]=kk[i].replace(/\-\./,"-0,").replace(/\./,",");if(kk[i].charAt(0)==",")kk[i]="0"+kk[i];}
	for(i=g;i>1;i--) if(k[i]!=0)t+="+"+kk[i]+v+"^"+i;
	if((k[1]!=0)&&(g>0))t+="+"+kk[1]+v; if(k[0]!=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";
	//if(g<4)t=t.replace(/\^3/g,"³").replace(/\^2/g,"²");
	return t.replace(/e - /g,"e-");
}

// k:Koeffizienten, g: Grad, t:Term
function Test(k,g,t,a)
{
	for(var i=0;i<20;i++)
	{
		var x=(Math.random()*40-20)/g;
		var y1=HornerR(k,g,x),y2=eval(t.replace(/X/g,"x"));//alert(x+"  "+(y1-y2));
		var A=a?y1:1;
		//alert("i="+i+"\nx="+x+"\ny1(Horner)="+y1+"\ny2(eval)="+y2+"\n"+t.replace(/X/g,"x")+"\n"+PStr("x",k,g));
		if(Math.abs((y1-y2)/A)>0.0000001)
		{
			return false;
		}
	}
	return true;
}

function HornerR(k,g,x)
{
	var y=k[g];
	for(var i=g-1;i>=0;i--)y=y*x+k[i];
	return y;
}

function HornerK(k,g,xr,xi,Y)
{//status="HornerK";
	var yr=k[g],yi=0;
	for(var i=g-1;i>=0;i--)
	{
		//xr·yr - yi·xi + kr + î·(yi·xr + xi·yr + ki)
		var yrr=yr*xr-yi*xi+k[i];
		yi=yi*xr+xi*yr;
		yr=yrr;
	}
	Y[0]=yr;Y[1]=yi;

}

function HornerKK(kr,ki,g,xr,xi,Y)
{
	var yr=kr[g],yi=ki[g];
	for(var i=g-1;i>=0;i--)
	{
		//xr·yr - yi·xi + kr + î·(yi·xr + xi·yr + ki)
		var yrr=yr*xr-yi*xi+kr[i];
		yi=yi*xr+xi*yr+ki[i];
		yr=yrr;
	}
	Y[0]=yr;Y[1]=yi;
}

function runden(x)
{
	return Math.round(x*10000000)/10000000;
}

function extrahiereNenner(t)
{
	var N="",k=0,x=(1==0), NN=new Array(),j,jj;
	t=t.replace(/ /g,"").toLowerCase();
	for(var i=0;i<t.length;i++)
	{
		if(t.charAt(i)=="/")
		{
			x=false,k=0;//alert(t.substring(i+1,t.length));
			for(j=i+1;j<t.length;j++)
			{
				var tt=t.charAt(j);
				if(tt=="(")k++;
				if(tt==")"){k--;if(k==0){j++;break;}if(k<0)break;}
				if(tt.toLowerCase()=="x")x=true;
				if((tt=="+")||(tt=="-")||(tt=="*")||(tt=="="))if(k==0)break;
			}
			var ttt=t.substring(i+1,j)
			if(x)
			{
				//if((ttt.charAt(0)=="(")&&(t.charAt(ttt.length-1)==")"))
				//N+=ttt; else 
				for(jj=0;jj<NN.length;jj++)if(NN[jj]==ttt)break;
				if(jj==NN.length){N+="("+ttt+")";NN[NN.length]=ttt;}
			}
			i=j;
		}
	}
	return N.replace(/\)\(/g,")*(");
}

function Newton_(xr,xi,k,kk,g,n,Y)
{
	var i;
	Y[0]=xr;Y[1]=xi;
	var d0=DNull_(xr,xi,k,g),d1,xrt=xr,xit=xi,yr,yi;
	var nwr=xr,nwi=xi;
	if(d0<1e-20)return true;
	//if(xr==""){nwr="";nwi="";return "";}
	for(i=0;i<n;i++)
	{
		HornerK(kk,g-1,xr,xi,Y);yyr=Y[0];yyi=Y[1];
		HornerK(k,g,xr,xi,Y);yr=Y[0];yi=Y[1];
		var N=(yyr*yyr+yyi*yyi);//if(N==0){break;}
		xrt-=(yr*yyr+yi*yyi)/N;
		xit+=(yr*yyi-yi*yyr)/N;
		if(Math.abs(xit)<1e-16)xit=0;
		Y[0]=xrt;Y[1]=xit;
		d1=DNull_(xrt,xit,k,g);
		//alert(L(xr,xi)+"\n"+L(xrt,xit)+"\n"+d0+"\n"+d1);
		if(d1>=d0){if(d0<1e-8)break;  return false;}
		d0=d1;
		xr=xrt;xi=xit;
		if(d0<1e-15)break;
	}
	nwr=xr;nwi=xi;
	//if(DNull_(runden(xr),runden(xi),k,g)<DNull_(xr,xi,k,g))nwr=runden(xr);nwi=runden(xi);
	Y[0]=nwr;Y[1]=nwi;
	return true;
}

function NewtonK_(xr,xi,kr,ki,g,n,Y)
{	
	var kkr=new Array(g),kki=new Array(g),i;
	Y[0]=xr;Y[1]=xi;
	for(i=0;i<g;i++){kkr[i]=kr[i+1]*(i+1);kki[i]=ki[i+1]*(i+1);}
	var d0=DNullK_(xr,xi,kr,ki,g),d1,xrt=xr,xit=xi,yr,yi;
	var nwr=xr,nwi=xi;
	if(d0<1e-20)return true;
	//if(xr==""){nwr="";nwi="";return "";}
	for(i=0;i<n;i++)
	{
		HornerKK(kkr,kki,g-1,xr,xi,Y);yyr=Y[0];yyi=Y[1];
		HornerKK(kr,ki,g,xr,xi,Y);yr=Y[0];yi=Y[1];
		var N=(yyr*yyr+yyi*yyi);//if(N==0){break;}
		xrt-=(yr*yyr+yi*yyi)/N;
		xit+=(yr*yyi-yi*yyr)/N;
		if(Math.abs(xit)<1e-30)xit=0;
		Y[0]=xrt;Y[1]=xit;
		d1=DNullK_(xrt,xit,kr,ki,g);
		//alert(L(xr,xi)+"\n"+L(xrt,xit)+"\n"+d0+"\n"+d1);
		if(d1>=d0){if(d0<1e-8)break;  return false;}
		d0=d1;
		xr=xrt;xi=xit;
		if(d0<1e-15)break;
	}
	nwr=xr;nwi=xi;
	Y[0]=nwr;Y[1]=nwi;
	return true;
}

function NewtonR_(x,k,kk,g,n)
{
	var i;
	var d0=Math.abs(HornerR(k,g,x)),d1,xt=x;
	var nw=x,y,yy,yyy;
	if(d0<1e-20)return x;
	for(i=0;i<n;i++)
	{
		y=HornerR(k,g,x);
		yy=HornerR(kk,g-1,x);
		if(yy==0){return false;}
		xt-=y/yy;
		yyy=HornerR(k,g,xt);
		//alert(x+"\n"+xt+"\n"+y+"\n"+yyy);
		if(y==yyy)break;
		d1=Math.abs(yyy);
		if((d1>d0)){if(d0<1e-12)break; return false;}
		d0=d1;
		x=xt;
		if(d0<1e-16){return x;}
	}
//	var rd=1000000000;
//	d0=Math.abs(HornerR(k,g,x))
//	while((Math.abs(HornerR(k,g,Math.round(x*rd)/rd))<=d0)&&(true))rd/=10;
	return false;
}


function DNull_(xr,xi,k,g)
{//status="DNull_";
	var y=new Array(0,0);//alert(g+"\n"+k+"\n"+L(xr,xi));
	HornerK(k,g,xr,xi,y);//alert(y);
	return Math.sqrt(y[0]*y[0]+y[1]*y[1]);
}

function DNullK_(xr,xi,kr,ki,g)
{
	var y=new Array(0,0);//alert(g+"\n"+kr+"\n"+ki+"\n"+L(xr,xi));
	HornerKK(kr,ki,g,xr,xi,y);//alert(y);
	return Math.sqrt(y[0]*y[0]+y[1]*y[1]);
}

function Ableitung(k,kk,g)
{
	for(var i=0;i<g;i++)kk[i]=k[i+1]*(i+1);
}

function sortiere(x,y,xl)
{
    var L_=new Array(32),R=new Array(32);
    var s, i, j, LL, rr, v, w, ii;
    s=0; L_[0]=0; R[0]=xl-1;
    do
    {
        LL = L_[s]; rr = R[s];
        s--;
        do
        {
            i = LL; j = rr;
            v = x[Math.floor((LL + rr) / 2)];
            do
		{
                while(x[i]<v) i++;
                while(x[j]>v) j--;
                if (i <= j)
                {
                    w = x[i]; x[i] = x[j]; x[j] = w;
                    w = y[i]; y[i] = y[j]; y[j] = w;
                    i++; j--;
                }
            } while (i <= j);
            if (j - LL >= rr - 1)
            {
                if (LL < j)
                {
                    s++;
                    L_[s] = LL; R[s] = j;
                }
                LL = i;
            }
            else
            {
                if (i < rr)
                {
                    s++;
                    L_[s] = i; R[s] = rr;
                }
                rr = j;
            }
        } while (LL < rr);
    } while (s >= 0);
	return x;
}


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(/\*x/g,v);
	p=p.replace(/xxxxxxxxxx/g,"x10").replace(/xxxxxxxxx/g,"x9");
	p=p.replace(/xxxxxxxx/g,"x8").replace(/xxxxxxx/g,"x7");
	p=p.replace(/xxxxxx/g,"x6").replace(/xxxxx/g,"x5");
	p=p.replace(/xxxx/g,"x4").replace(/xxx/g,"x3").replace(/xx/g,"x2");
	//p=p.replace(/x0/g,"*1");
	var pp=p.replace(/\d/g,"¶").replace(/,/g,"¶").replace(/\./g,"¶").replace(/p/g,"¶").replace(/_/g,"¶");
	var ppp=pp.replace(/\//g,"¶").replace(/\*/g,"¶");
	var i,je,jk,k,e,jj;
	var b=0;
	for(i=0;i<K.length;i++)K[i]=0;
	for(i=0;i<p.length;i++)
	{
		if(pp.charAt(i)!=v)continue;
		for(jk=i-1;jk>=0;jk--) {if(ppp.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));
		for(jj=je;jj<pp.length;jj++)
		{	
			if(jj==ppp.length-1)jj++;
			if((ppp.charAt(jj)=="+")||(ppp.charAt(jj)=="-")||(jj==ppp.length))
			{
				if(jj>je)
				{
					pp=pp.substr(0,i)+pp.substring(je,jj)+pp.substring(i,je)+pp.substring(jj,pp.length); 
					ppp=ppp.substr(0,i)+ppp.substring(je,jj)+ppp.substring(i,je)+ppp.substring(jj,pp.length); 
					p=p.substr(0,i)+p.substring(je,jj)+p.substring(i,je)+p.substring(jj,p.length);
					i+=(jj-je);je=jj;
				}
				break;
			}
		}
		if((je==i+1))e=1; 
		if(p.charAt(jk)=="/")
		{
			for(jk=jk-1;jk>=0;jk--) {if(pp.charAt(jk)!="¶")break;}
			b=eval(p.substring(jk,i));
		}
		else if((k!=Math.floor(k))||(p.substring(jk,i).indexOf("p")>-1))
		{
			var b=eval(p.substring(jk,i));
		}
		else
		{
			b=k;
		}
		if(e>K.length-1)for(var ii=K.length;ii<=e;ii++)K[ii]=0;
		K[e]+=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=eval(pp);
	//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;}	
	if(!isNaN(b))K[0]+=b;
	//	alert("parse: "+PPP+"\n"+K[0].str());
	
}

function polydivR(k,g,x0)
{ 
	q=new Array(g);
	kk=new Array(g+1);
	var i,gg=g;
	for(i=0;i<kk.length;i++)kk[i]=k[i];
	for(i=0;i<kk.length-1;i++)q[i]=0;
	while(g>0)
	{
		kk[g-1]+=kk[g]*x0;
		q[g-1]=kk[g];
		kk[g]=0;
		while((kk[g]==0)&&(g>0))g--;
	}
	if((Math.abs(kk[g])>1e-8)||(g>0)){return false;}
	k[gg]=0;
	for(i=0;i<q.length;i++)k[i]=q[i];
	return true;
}
function polydivRK(k,g,xr,xi)
{
	q=new Array(g);
	kk=new Array(g+1);
	var i,gg=g,a=-2*xr,b=xr*xr+xi*xi;
	for(i=0;i<kk.length;i++)kk[i]=k[i];
	for(i=0;i<kk.length-1;i++)q[i]=0;
	while(g>0)
	{
	 	//status="Polynomdivision, g="+g+"  Rest: "+PStr("x",kk,gg);
		if(g>1)q[g-2]=kk[g];
		kk[g-1]-=kk[g]*a;
		if(g>1)kk[g-2]-=kk[g]*b;
		kk[g]=0;
		//alert("g: "+g+"\nq: "+q.join("  ")+"\nk: "+kk.join("  "));
		while((kk[g]==0)&&(g>0))g--;
	}
	//alert("fertig\ng="+g+"\nq: "+q.join("  ")+"\nk: "+kk.join("  "));
	//if((Math.abs(kk[0])>1e-8)||(Math.abs(kk[1])>1e-8)||(g>0)){return false;}
	k[gg]=0;
	for(i=0;i<q.length;i++)k[i]=q[i];
	return true;
}


function polydivK(kr,ki,g,xr,xi)
{
	if(g<=1) return;
	qr=new Array(g+1),qi=new Array(g+1);
	kkr=new Array(g+1),kki=new Array(g+1);
	var i,gg=g;
	for(i=0;i<kkr.length;i++){kkr[i]=kr[i];kki[i]=ki[i];}
	for(i=0;i<kkr.length;i++){qr[i]=0;qi[i]=0;}
	while(g>0)
	{
		qr[g-1]=kkr[g];
		qi[g-1]=kki[g];
		//alert("kkr[g-1]="+kkr[g-1]+"\nqr[g-1]*xr="+qr[g-1]*xr+"\nqi[g-1]*xi="+qi[g-1]*xi);
		kkr[g-1]+=qr[g-1]*xr-qi[g-1]*xi;
		kki[g]-=qi[g-1];
		kkr[g]=0;
		kki[g-1]+=xi*qr[g-1]+xr*qi[g-1];
		//while((kkr[g]==0)&&(g>0))
		g--;
	}
	if((Math.abs(kkr[g])>1e-12)||(g>0)){return false;}
	kr[gg]=0;
	alert("Fertig:\nqr: "+qr.join("  ")+"\nqi: "+qi.join("  ")+"\nkkr: "+kkr.join("  ")+"\nkki: "+kki.join("  "));
	for(i=0;i<qr.length;i++){kr[i]=qr[i];ki[i]=qi[i];}
	return true;
}
function testpolydivK()
{
	var kr=new Array(-195,34,6,-6,1),
          ki=new Array(0,0,0,0,0),
	     y=new Array(0,0);

	polydivRK(kr,4,2,3);alert(kr);
}


function Zufallsterm()
// g: Grad, max: maximaler Koeffizient
// p0: Wahrscheinlichkeit für K[i]=0, K: Koeffizienten
{
	var t="";
	do
	{
	var g=Math.floor(Math.random()*7+2),max=10,p0=.3+1/g,K=new Array();
	if(Math.random()>.7){g=Math.floor(Math.random()*15+5);p0=.5;}
	for(var i=0;i<=g;i++)
	{
		if((Math.random()<p0)&&(i<g)) K[i]=0;
		else
		{
			K[i]=Math.floor(Math.random()*max);
			if(Math.random()<.5)K[i]=-K[i];
		}
	}
	t=PStr("x",K,g);
	}while((t.length<10)||(t.length>55))
	document.f.inp.value=t;
	document.f.normalform.value="";
	//solvePolynom();
	document.f.ngl.value="";
//	document.f.x44.focus();
//	document.f.inp.focus();
	document.f.solvebutton.focus;
}

function clear(k)
{
	for(var i=0;i<k.length;i++)k[i]=0;
}

function blinkoff()
{for(var i=0;i<3;i++)document.images[i].src="../bilder/blink_off.gif";}