// INTERPOLATION
// Program 5 : To impliment Newton's Forward 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 h;			// constant difference
	double x, y = 0;	// y is f(x)
	double u, m = 1.0; 	// m is multiplier
	
	printf(" Enter no of terms : ");
	scanf("%d", &n);
	printf(" Enter first term : ");
	scanf("%lg", &table[0][0]);
	printf(" Enter difference between terms : ");
	scanf("%lg", &h);
	
	for( i=0; i<n; i++)
	{
		// calculate other x from first term and difference
		table[i][0] = table[0][0] + (double)(i) * h;
		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];
	
	printf("\n Enter the value of x for which you want to find f(x) : ");
	scanf("%lg", &x);
	
	u = ( x - table[0][0] ) / h;
	printf("\n u = %g", u);
	
	for( j=1; j<=n; j++)
	{
		y += m * table[0][j];
		m *= u / (double)(j);
		u--;
	}
	
	printf("\n F(%g) = %g", x, y);	
	getch();
}