// INTERPOLATION
// Program 12 : To impliment Newton's Divided Difference interpolation formula
// ------------------------------------------------------------------------
//
// Table: I use only one 2D array to store all values of x, y and delta y's
// Logic ( i and j are the loop variables )
//	
//	  i\j |   0  |   1  |   2   |   3     |   4  |
//	  ----+------+------+-------+---------+------+...
//	   0  |  x1  |  y1  | y2-y1 | dy2-dy1 |      |
//	  ----+------+------+-------+---------+------+...
//	   1  |  x2  |  y2  | y3-y2 |         |      |
//	  ----+------+------+-------+---------+------+...
//	   2  |  x3  |  y3  |       |         |      !
//	  ----+------+------+-------+---------+...
//	      !      !      !       !         !      

#include <stdio.h>
#include <conio.h>

#define MAXITEMS 10

main()
{
	int i,j;	// for loop
	int n;		// no of terms
	// 2D array. 1st column for x, 2nd for y and other for difference
	double table[MAXITEMS][MAXITEMS+1];
	double x, y = 0;	// y is f(x)
	double m = 1.0; 	// m is multiplier
	
	printf(" Enter no of terms : ");
	scanf("%d", &n);
	
	for( i=0; i<n; i++)
	{
		printf(" Enter x%d : ", i);
		scanf("%lg", &table[i][0]);
		printf(" Enter the value of f(%lg) : ", table[i][0]);
		scanf("%lg", &table[i][1]);
	}
	
	for( j=1; j<n; j++)	// loop to each column
		for( i=0; i<n-j; i++)	// loop to cell within a column
			table[i][j+1] = (table[i+1][j] - table[i][j])
			               /(table[j+i][0]-table[i][0]);
	
	printf("\n Enter the value of x for which you want to find f(x) : ");
	scanf("%lg", &x);
	
	for( j=1; j<=n; j++)
	{
		y += m * table[0][j];
		m *= (x - table[j-1][0]);
	}
	
	printf("\n F(%g) = %g", x, y);	
	getch();
}