public class PolyLegendre{
int n;
int N;
double[] Racines;	
double[] Valeurs;
double[] ValeursD;


PolyLegendre(int nn, int NN)
{n=nn;
N=NN;
double h=2.0/(N-1);
if (n==0)
{
Racines=null;
Valeurs=new double[N];
for (int i=0;i<N;i++)
Valeurs[i]=1.0;
}
else if (n==1)
{
Racines=new double[1];
Racines[0]=0;
Valeurs=new double[N];
for (int i=0;i<N;i++)
Valeurs[i]=-1.0+i*h;
}
else 
{
	Valeurs=new double[N];
	ValeursD=new double[N];
	Racines=new double[n];
for (int i=0;i<N;i++)
{
Valeurs[i]= valeur(-1.0+i*h);
ValeursD[i]= valeurD(-1.0+i*h);
}
//rempliRacinesNewton();
//tri();
//reRempliRacinesNewton();
rempliRacines();

}
}



public double valeur(double x){
double ln0,ln1,ln2;
if (x==-1.0)
{
if ((n&1)==1)
return -1.0;
else
return 1.0;
}
else if (x==1.0)
return 1.0;
else if ((x==0)&&((n&1)==1))
return 0;
else
{
ln0=1.0;
ln1=x;
ln2=0.0;
for(int k=0;k<=n-2;k++)// REMETTRE n
{ln2=((double)(2*k+3)/(double)(k+2))*ln1*x-((double)(k+1)/(double)(k+2))*ln0;
ln0=ln1;
ln1=ln2;
}
return ln2;
	}
}

public double valeurD( double x){
double ln0,ln1,ln2,ln0p,ln1p,ln2p;

ln0=1.0;
ln1=x;
ln0p=0.0;
ln1p=1.0;
ln2p=0.0;
for(int k=0;k<=n-2;k++)
{ln2=((double)(2*k+3)/(double)(k+2))*ln1*x-((double)(k+1)/(double)(k+2))*ln0;
ln2p=((double)(2*k+3)/(double)(k+2))*ln1+((double)(2*k+3)/(double)(k+2))*x*ln1p-((double)(k+1)/(double)(k+2))*ln0p;
ln0=ln1;
ln1=ln2;
ln0p=ln1p;
ln1p=ln2p;
}
return ln2p;
	}

public double newton(double x0, double eps,int nmax){
double xn=x0;
int i=0;
System.out.println(xn);
while ((Math.abs(valeur(xn))>eps) && (i<nmax))
{
xn=xn-valeur(xn)/valeurD(xn);
//System.out.println(valeur(xn));
i++;
}
return xn;
}
public double dichotomie(double x0, double x1,double eps,int nmax){
double an=x0;
double bn=x1;
int i=0;
double xn=an-valeur(an)*(bn-an)/(valeur(bn)-valeur(an));
while ((Math.abs(valeur(xn))>eps) && (i<nmax))
{
	if (valeur(an)*valeur(xn)<0)
	bn=xn;
	else
	an=xn;
xn=an-valeur(an)*(bn-an)/(valeur(bn)-valeur(an));
System.out.println(valeur(xn));
i++;
}
System.out.println(i);

return xn;
}

public void rempliRacines(){
double eps=0.001;
double hh=1.0/(10000.0*n);	
double x0=-1.0;
//System.out.println("valeur de "+x0);
//System.out.println("valeur de Ln"+ valeur(x0));
int i=0;
int I= Math.round((int)(n/2.0))-1;
while(i<=I)
{while ((Math.abs(valeur(x0))>eps)&&(x0<-hh))
x0=x0+hh;
//System.out.println("valeur de "+x0);
//System.out.println("valeur de Ln"+ valeur(x0));
if (Math.abs(valeur(x0))<eps)
Racines[i]=x0;
else
Racines[i]=-10;
i++;
x0=x0+2/(5.0*(n-1));
}
if((n&1)==1)
Racines[I+1]=0.0;
for(i=0;i<=I;i++)
Racines[n-1-i]=-Racines[i];
}
 



public void rempliRacinesDic(){
double eps=0.001;
double hh=2.0/(4.0*n);	
double x0=-1.0;
double x1=-1.0+hh;
int i=0;
while(i<n)
{
while ((valeur(x0)*valeur(x1)>eps)&&(x1<1.0))
x1=x1+hh;
if (Math.abs(valeur(x1))<eps)
{Racines[i]=x1;
x0=x1+(1.0/n-1);
x1=x1+hh;
}
else if (valeur(x0)*valeur(x1)<-eps)
{Racines[i]=dichotomie(x0,x1,eps,1000);
x0=x1;
x1=x1+hh;
}
i++;
}
 

}

public void rempliRacinesNewton(){
double hh=1.0/n;
if ((n&1)==1)	
{
for (int i=0;i<(n-1)/2;i++)
{
Racines[i]=newton(Math.cos(Math.PI*(1-i*hh)),0.0001,1000);
Racines[n-1-i]=-Racines[i];
}
Racines[(n-1)/2]=0.0;
}
else	
{
for (int i=0;i<n/2;i++)
{
Racines[i]=newton(Math.cos(Math.PI*(1-i*hh)),0.0001,1000);
Racines[n-1-i]=-Racines[i];
}

}
}



public void reRempliRacinesNewton(){
double hh=1.0/(3*n);
System.out.println("ok");
if ((n&1)==1)	
{
for (int i=1;i<((n-1)/2);i++)
{
 if (((Racines[i-1]!=Racines[i]))&&(Math.abs(Racines[i]-Racines[i+1])<0.0001)&&(valeurD(Racines[i])*valeurD(Racines[i+1])>0))
{
Racines[i]=dichotomie(Racines[i-1]+hh,Racines[i+1]-hh,0.0001,1000);
Racines[n-1-i]=-Racines[i];
System.out.println("ok2");
}
else
{
System.out.println(i);
System.out.println(Racines[i-1]);
System.out.println(Racines[i]);
System.out.println(Racines[i+1]);
System.out.println(Math.abs(Racines[i]-Racines[i+1])<0.0001);
}
}
}
else	
{
for (int i=1;i<n/2-1;i++)
{
if (((Racines[i-1]!=Racines[i+1]))&&(Racines[i]==Racines[i+1])&&(valeurD(Racines[i])*valeurD(Racines[i+1])>0))
Racines[i]=dichotomie(Racines[i-1]+hh,Racines[i+1]-hh,0.0001,1000);

Racines[n-1-i]=-Racines[i];
}

}
}


public void afficherValeurs(){
for (int i=0;i<N;i++)
{
System.out.println(Valeurs[i]);
}
}

public void afficherRacines(){
	System.out.println("Affichage des racines du polynome "+n);
for (int i=0;i<n;i++)
{
System.out.println(Racines[i]);
}
}

public void tri(){
double s,d;
for(int i=0; i<n-1;i++)
	if (Racines[i]>Racines[i+1])
	{ s=Racines[i+1];
	  Racines[i+1]=Racines[i];
	  Racines[i]=s;
    for(int j=i-1; j>-1;j--)
      if (Racines[j]>Racines[j+1])
	      { d=Racines[j];
	        Racines[j]=Racines[j+1];
	        Racines[j+1]=d; 
	      }
   }
  }

public double[] recupValeurs(){
double x[]= new double[N];
x= Valeurs;
return x;
}

public double eletRacine(int i){

return Racines[i];
}

}