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

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

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

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

void main()
{
   float xn,yn;
   float x[MAX],y[MAX],bd[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);
   
   //--------------------------
   
   xn=x[n-1];      
   yn=y[n-1];      

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

   s=(l-xn)/h;   

   //--------------------------
   // BD TABLE
   for(i=1;i<n;i++) 
      bd[n-i][0]=y[n-i]-y[n-i-1]; 
  
   for(j=1;j<n-1;j++) // 1 to n-1
   {
      for(i=1;i<n-j;i++)
     bd[n-i][j]=(bd[n-i][j-1])-(bd[n-i-1][j-1]);
   }
   //--------------------------
  
   y_inp=yn;

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

   printf("\n\n\nResult by Newton's Backward interpolation formula :%.3f",y_inp);
   getch();

} // end of main

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