Implementation of NBDF ( Newtons backward difference formula ) in C program

The above table shows the values which are to be calculated by subtracting the corresponding values in the preceding column, and then substituted in the formula given below:

Here, p= (x-x0) /h   ; h=common difference;

After substituting the differences and calculations we will obtain the highly probable value of the function at the given point.

So , now heading for the program:

The program contains : 2 recursive functions and one driver function (main())

Recursive functions:

int fact(int num){
     if(num==0)
         return 1;
     return num*fact(num-1);
 }

this functions will return the factorial of the value which is passed to it through actual parameters.

and another function float pinc() :

float pinc(float p,float pf){
     if(fabs(p-pf)<0.05)
         return p;
     else return p*pinc(p-1,pf);
 }

which accepts two arguments p=higher value and pf=lower value , for example:

In the term p(p+1)(p+2)(p+3)(p+4)........(p+n-1) : p=p and pf=p+n-1 and with the help of recursion the returning value is continuously multiplied by pf-1 value until pf becomes p or (p~pf).

Now to calculate the difference and to show the difference table , we will use matrix of order (nxn) where n=number of points given.

p=(x1-x[n-1])/(x[1]-x[0]);
     for(int i=1;i<n+1;i++)
         for(int j=1;j<n;j++)
             if(y[j][i-1]!=0 && y[j-1][i-1]!=0)
                 y[j][i]=y[j][i-1]-y[j-1][i-1];
     printf("\n                                    TABLE\n\n");
     for(int i=0;i<n;i++){
         for(int j=0;j<n+1;j++)
             if(y[i][j]!=0)
                 printf("%.2f   ",y[i][j]);
         printf("\n");
     }

In the above code , the difference's are stored in a matrix of order (nxn) (y[n][n]) and then they are printed on the user screen , such that when the difference is 0 ,space is printed.

now ,we only have to deal with the substitution of the differences in the formula, to do this we will repetitively add each term in the res variable ,as shown in the code below:

 
 while(c<n && value!=0){
  value=n-1;
  while(y[value][c]==0 && value>=0)
   value--;
  value=y[value][c];
  res+=(pinc(p+c-1,p)*value)/fact(c);  
  c++;
  
 }

The result value is calculated with the help of recursive functions pinc() and fact()

res+=(pinc(p+c-1,p)*value)/fact(c);

Source Code:

//NBDF BY: JATIN YADAV
#include <stdio.h>
#include<stdlib.h>
#include<math.h>
float pinc(float p,float pf){
 if(fabs(p-pf)<0.05)
  return p;
 else return p*pinc(p-1,pf);
}
int fact(int num){
 if(num==0)
  return 1;
 return num*fact(num-1);
}
int main(int argc, char *argv[]) {
 int n;
 float x1,res=0,p;
 printf("********************NBDF************************\n");
 printf("\nEnter the number of data:\t");
 scanf("%d",&n);
 float *x=(float*)calloc(n,sizeof(float));
 float *y[n];
 for(int i=0;i<n;i++)
  y[i]=(float*)calloc(n,sizeof(float)); 
 printf("\nEnter data:\n");
 for(int i=0;i<n;i++)
  scanf("%f%f",&x[i],&y[i][0]);
 printf("\nEnter the value where funtion value is to be found:\t");
 scanf("%f",&x1);
 p=(x1-x[n-1])/(x[1]-x[0]);
 for(int i=1;i<n+1;i++)
  for(int j=1;j<n;j++)
   if(y[j][i-1]!=0 && y[j-1][i-1]!=0)
    y[j][i]=y[j][i-1]-y[j-1][i-1];
 printf("\n                                    TABLE\n\n");
 for(int i=0;i<n;i++){
  for(int j=0;j<n+1;j++)
   if(y[i][j]!=0)
    printf("%.2f   ",y[i][j]);
  printf("\n");
 }
 int c=1,value=1;
 res=y[n-1][0];
 
 while(c<n && value!=0){
  value=n-1;
  while(y[value][c]==0 && value>=0)
   value--;
  value=y[value][c];
  res+=(pinc(p+c-1,p)*value)/fact(c);  
  c++;
  
 }
 
 printf("\n\n Result= %f",res);
 printf("\n\n\n********************Made By: Jatin Yadav*******************\n");
 int temp;
 scanf("%d",&temp);
 free(x);
 free(y);
 return 0;
}

Here is the executable program: https://www.dropbox.com/s/zg493gpztubjweg/NBDFC.exe?dl=0

if you want to learn more about " Newtons backward difference formula " or you need a presentation on this topic you can download the power point presentation ( PPT ) by clicking here ;

if any doubts or queries please comment