#include <stdio.h>
#include <math.h>
/* lagran.c : 1999 3 9 by Oguni */
#define N 6
#define M 21
main(){
  double x[N]={1.,5.,11.,15.,19.,21.};
  double y[N]={1.,3.,5.,7.,15.,21.};
  double xnew[M], ynew[M];
  int i, n=6, m=21;
  for (i=0; i<m; i++){ xnew[i]=(double)i; }
  lagran(x,y,xnew,ynew,n,m);
  printf("estimated values\n");
  for (i=0; i<m; i++){
    printf("%f %f\n", xnew[i], ynew[i]); }
}
/* function */
lagran(x,y,xnew,ynew,n,m)
double x[N],y[N],xnew[M],ynew[M];
int n,m;
{
  double l[N], xbar[N], s;
  int i,j,k;
  for (j=0; j<m; j++){
    for (i=0; i<n; i++){
      for (k=0; k<n; k++){
        if (i!=k) xbar[k]=(xnew[j]-x[k])/(x[i]-x[k]);
        else xbar[k]=1.;
      }
      l[i]=1.0;
      for (k=0; k<n; k++){ l[i]*=xbar[k]; }
    }
    s=0.0;
    for (k=0; k<n; k++){
      s+=y[k]*l[k]; }
    ynew[j]=s;
  }
  return;
}