Skip to content

Instantly share code, notes, and snippets.

@karngyan
Created February 19, 2019 11:01
Show Gist options
  • Save karngyan/482336c70e69e4ef87a656f8d29a35a8 to your computer and use it in GitHub Desktop.
Save karngyan/482336c70e69e4ef87a656f8d29a35a8 to your computer and use it in GitHub Desktop.
Shows Simplified Polynomial as well.
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<stdbool.h>
#define N 1010
typedef struct pt
{
double x , y;
} pt;
pt a[N];
double A[N];
void gen(int n , double roots[N] , double tmp)
{
double coeff[N];
int i , j;
for(i = 0 ; i<=n ; ++i)
coeff[i] = 0;
coeff[n] = 1;
for(i = 1; i<=n ; ++i)
{
for(j = n - i - 1 ; j<n ; ++j)
{
coeff[j] = coeff[j] + (-1)*roots[i-1]*coeff[j+1];
}
}
for(i = n ; i>=0 ; --i)
{
A[i] += (coeff[i]*tmp);
}
}
void make_polynomial(int n)
{
double tmp;
int i , j , k;
double roots[N];
printf("\nP(X) = ");
for(i = 0 ; i<=n ; ++i)
A[i] = 0;
for(i = 1 ; i<=n ; ++i)
{
tmp = a[i].y;
k = 0;
for(j = 1 ; j<=n ; ++j)
{
if(i == j)
continue;
tmp = tmp * (1.0 / (a[i].x - a[j].x));
roots[k++] = a[j].x;
}
gen(n-1 , roots , tmp);
}
for(i = n-1 ; i>=0 ; --i)
{
// if(fabs(A[i]) < 0.0000001)
// continue;
if(i == 0)
printf("(%.2lf)" , A[i]);
else if(i == 1)
printf("(%.2lf)*(X) + " , A[i]);
else
printf("(%.2lf)*(X^%d) + " , A[i] , i);
}
printf("\n");
}
double interpolate(double x , int n)
{
double res = 0.0 , tmp;
int i , j;
for(i = 1 ; i<=n ; ++i)
{
tmp = a[i].y;
for(j = 1 ; j<=n ; ++j)
{
if(i == j)
continue;
tmp = tmp * ( (x - a[j].x) / (a[i].x - a[j].x) );
}
res+=tmp;
}
return res;
}
signed main()
{
int n , i;
double x;
printf("\t--Langrange\'s Interpolation--\n\n");
printf("Enter number of data points: ");
scanf("%d" , &n);
printf("\nEnter the data points:\n");
for(i = 1 ; i<=n ; ++i)
scanf("%lf %lf" , &a[i].x , &a[i].y);
make_polynomial(n);
printf("\n\nEnter value of x: ");
scanf("%lf" , &x);
printf("\nP(%.0lf) = %.4lf\n" , x , interpolate(x , n));
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment