/******************************************

    NEWTON'S FORWARD INTERPOLATION
    http://native-code.blogspot.com

 ******************************************/

#include<stdio.h>
#include<conio.h>
#define MAX 20

void main()
{
   float x0,y0;
   float x[MAX],y[MAX],fd[MAX][MAX];
   float h,l,s, y_inp,p,fact;
   int i,n,j,k;
   
   p=fact=1.0F;
   clrscr();
   //--------------------------
   
   printf("\nEnter the total number of pairs:");
   scanf("%d",&n);
    
   printf("\n\nEnter the table");
   printf("\nX\tY\n");
   
   for(i=0;i<n;i++)
   {
      scanf("%f",(x+i));
      scanf("%f",(y+i));
   }
   
   //--------------------------
   
   printf("\nEnter the value of X at which to find Y:");
   scanf("%f",&l);
   
   //--------------------------
   
   x0=x[0];      //ok
   y0=y[0];      //ok

   h=x[1]-x[0];  //ok

   s=(l-x0)/h;   //ok

   //--------------------------
   // FD TABLE
   for(i=0;i<n-1;i++) // 0 to n-1
      fd[i][0]=y[i+1]-y[i]; // col is fixed at 0
  
   for(j=1;j<n-1;j++) // 1 to n-1
   {
      for(i=0;i<n-1-j;i++)
     fd[i][j]=(fd[i+1][j-1])-(fd[i][j-1]);
   }
   //--------------------------
  
   y_inp=y0;

   for(k=1;k<n;k++)
   {
      p=p*(s-k+1);
      fact = fact*k;
      y_inp=y_inp+(p/fact)*fd[0][k-1];
   }

   printf("\n\n\nresult by Newton's Forward Interpolation formula:%.3f",y_inp);
   getch();

} // end of main

/* http://native-code.blogspot.com */