### 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

__variable ,as shown in the code below:__**res**```
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

Great content! Can you please post about linked list insertion and deletion. Thanks!

ReplyDelete