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


void main()
{
    FILE *fp;
    int number,i,j,k=0,m;
    float xvalue[MAX],yvalue[MAX],search;
    float differ[MAX][MAX],uvalue,hvalue,product,sum;
    fp=fopen("nwddi.dat","w");
    clrscr();
    printf("\n\n");
    fprintf(fp,"\n\n");
    printf("How many numbers you want to enter for x  : ");
    fprintf(fp,"How many numbers you want to enter for x  : ");
    scanf("%d",&number);
    fprintf(fp,"%d",number);
    for(i=0;i<number;i++)
    {
        printf("\nEnter value for x(%d)  : ",i);
        fprintf(fp,"\nEnter value for x(%d)  : ",i);
        scanf("%f",&xvalue[i]);
        fprintf(fp,"%f",xvalue[i]);
        printf("\nEnter value for y(%d)  : ",i);
        fprintf(fp,"\nEnter value for y(%d)  : ",i);
        scanf("%f",&yvalue[i]);
        fprintf(fp,"%f",yvalue[i]);
    }
    printf("\nEnter any value of x for which you want to find y : ");
    fprintf(fp,"\nEnter any value of x for which you want to find y : ");
    scanf("%f",&search);
    fprintf(fp,"%f",search);
    if(search<xvalue[0] || search>xvalue[number-1])
    {
        printf("\n\nValue lies outside the given values of x ");
        fprintf(fp,"\n\nValue lies outside the given values of x ");
        getch();
        exit(1);
    }
    else
    {
        clrscr();
        printf("\n\nNEWTON'S DIVIDED DIFFERENCE INTERPOLATION ");
        fprintf(fp,"\n\nNEWTON'S DIVIDED DIFFERENCE INTERPOLATION ");
        for(j=0;j<number-1;j++)
        {
            for(i=0;i<number-(j+1);i++)
            {
                if(j==0)
                {
                    differ[i][j]=(yvalue[i+1]-yvalue[i])/(xvalue[i+1]-xvalue[i]);
                }
                else
                {
                    differ[i][j]=(differ[i+1][j-1]-differ[i][j-1])/(xvalue[i+(j+1)]-xvalue[i]);
                }
            }
        }
        printf("\n\n");
        fprintf(fp,"\n\n");
        printf(" x       y   ");
        fprintf(fp," x       y   ");
        for(i=1;i<number;i++)
        {
            printf("   d^%dy(i) ",i);
            fprintf(fp,"   d^%dy(i) ",i);
        }
        printf("\n\n");
        fprintf(fp,"\n\n");
        for(i=0;i<number;i++)
        {
            printf(" %.2f    %.2f  ",xvalue[i],yvalue[i]);
            fprintf(fp," %.2f    %.2f  ",xvalue[i],yvalue[i]);
            for(j=0;j<number-(i+1);j++)
            {
            printf("  %.4f  ",differ[i][j]);
            fprintf(fp,"  %.4f  ",differ[i][j]);
            }
            printf("\n");
            fprintf(fp,"\n");
        }
        for(i=0;i<number;i++)
        {
            if(search>xvalue[i])
            {
                k=k+1;
            }
        }
        k=k-1;
        sum=yvalue[k];
        for(i=0;i<number-(k+1);i++)
        {
            product=1;
            for(j=0;j<=i;j++)
            {
                product=product*(search-xvalue[j+k]);
            }
            sum=sum+(differ[k][i]*product);

        }
        printf("\n\n");
        fprintf(fp,"\n\n");
        printf("Interpolated value is  :  %f  ",sum);
        fprintf(fp,"Interpolated value is  :  %f  ",sum);
    }
    fclose(fp);
    getch();
}