### Thread: Newtons forward interpolation problem help

1. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2013
Posts
34
Rep Power
2

#### Newtons forward interpolation problem help

The following try of this problem is
Code:
#include&lt;stdio.h&gt;
#include&lt;process.h&gt;
int n;
int k=0;
int b[50];
int c[50];
int s[50];
float r;
int func(int a)
{
if(a==0)
return 1;
else
return a*func(a-1);
}
float fun(int b)
{
if(b==0)
return 1;
else
{
r--;
b--;
return r*fun(b);
}
}
void recur(int x[])
{
int i;
for(i=0; i&lt;n-1; i++)
c[i]=x[i+1]-x[i];
b[k]=c[0];
if(b[k]!=0)
{
k++;
n--;
recur(c);
}
}
int main()
{
int i;
float p;
int a[50],h;
float y;
printf("how many values to enter");
scanf("%d",&n);
scanf("%d",&a[0]);
scanf("%d",&a[1]);
for(i=2; i&lt;=n-1; i++)
{
scanf("%d",&a[i]);
if((a[i]-a[i-1])!=(a[i-1]-a[i-2]))
exit(0);
h=a[i]-a[i-1];
}
printf("enter frequencies");
for(i=0; i&lt;n; i++)
scanf("%d",&s[i]);
recur(s);
printf("find which value to find");
scanf("%d",&p);
r=(p-a[0])/h;
i=0;
y=s[0];
while(i&lt;n)
{
y=y+(r*fun(i)*b[i])/(func(i));
i++;
}
printf("%f",y);
return 0;
}

If i input a as 1,2,3,4,5,6 and
s as 6,7,8,9,10 and the value p as 2.5 i am not getting the correct result please help
Ps:i think my float-int conversion is wrong in the step where i calculate the value of r.Please help
2. float p;
/*...*/
scanf("%d",&p);

p is float. You've read the float with integer format.
gcc -Wall
warns me.

Also, you purposefully use only a[0] and a[1]. Why would anyone want to enter more values? Are a[0] and h better choices?

Also you told us to enter 6 values for array a and 5 values for s. Why should you requesting assistance need to be less careful than a responder?

What is the output you expect? In somewhat compressed form so that all lines fit on my tiny display:
Code:
```#include<stdio.h>
#include<stdlib.h>
int n, k=0, b[50], c[50], s[50];
float r;
int func(int a) {
return a ? a*func(a-1) : 1;
}
float fun(int b) {
if (!b)
return 1;
r--, b--;
return r*fun(b);
}
void recur(int*x) {
int i;
for(i=0; i < n-1; i++)
c[i]=x[i+1]-x[i];
b[k]=c[0];
if(b[k]!=0) {
k++;
n--;
recur(c);
}
}
int main() {
int i,a[2],h;
float p, y;
puts("how many frequencies?"); /* fail as soon as possible */
scanf("%d",&n);
if ((n < 2) || (50 < n)) {
fputs("\n2 to 50\n", stderr);
exit(0);
}
puts("enter a[0] and a[1].  The difference a[1]-a[0] is step size h.");
scanf("%d %d",a+0, a+1);
h = a[1]-a[0];
puts("enter frequencies");
for(i=0; i<n; i++)
scanf("%d",s+i);
recur(s);
puts("find which value to find");
scanf("%f",&p);
r=(p-a[0])/h;
i=0;
y=s[0];
for (i = 0; i<n; ++i)
y=y+(r*fun(i)*b[i])/(func(i));
printf("%f",y);
return 0;
}```
Wow. Nice code tags! Wow. No more &lt; . How do you people get by? Mysterious.

• tendoeschate agrees
Last edited by b49P23TIvg; January 30th, 2014 at 04:21 PM. Reason: replaced for printf, puts.
3. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2013
Posts
34
Rep Power
2
Originally Posted by b49P23TIvg
float p;
/*...*/
scanf("%d",&p);

p is float. You've read the float with integer format.
gcc -Wall
warns me.

Also, you purposefully use only a[0] and a[1]. Why would anyone want to enter more values? Are a[0] and h better choices?

Also you told us to enter 6 values for array a and 5 values for s. Why should you requesting assistance need to be less careful than a responder?

What is the output you expect? In somewhat compressed form so that all lines fit on my tiny display:
Code:
```#include<stdio.h>
#include<stdlib.h>
int n, k=0, b[50], c[50], s[50];
float r;
int func(int a) {
return a ? a*func(a-1) : 1;
}
float fun(int b) {
if (!b)
return 1;
r--, b--;
return r*fun(b);
}
void recur(int*x) {
int i;
for(i=0; i < n-1; i++)
c[i]=x[i+1]-x[i];
b[k]=c[0];
if(b[k]!=0) {
k++;
n--;
recur(c);
}
}
int main() {
int i,a[2],h;
float p, y;
puts("how many frequencies?"); /* fail as soon as possible */
scanf("%d",&n);
if ((n < 2) || (50 < n)) {
fputs("\n2 to 50\n", stderr);
exit(0);
}
puts("enter a[0] and a[1].  The difference a[1]-a[0] is step size h.");
scanf("%d %d",a+0, a+1);
h = a[1]-a[0];
printf("enter frequencies");
for(i=0; i<n; i++)
scanf("%d",s+i);
recur(s);
printf("find which value to find");
scanf("%f",&p);
r=(p-a[0])/h;
i=0;
y=s[0];
for (i = 0; i<n; ++i)
y=y+(r*fun(i)*b[i])/(func(i));
printf("%f",y);
return 0;
}```
Wow. Nice code tags! Wow. No more &lt; . How do you people get by? Mysterious.

Thanks mate
4. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2013
Posts
34
Rep Power
2
for the input
0
1
2
3
4
and the frequencies
1
7
23
55
109
and value as 0.5 i am not getting the correct output
5. The program correctly computes the answer 6.5 .

(Actually it's wrong. You haven't gotten the message: supply the expected result!)

Solving the problem with executable Iverson notation, the most recent dialect of APL, an interactive, multiple-instruction-single-data language giving a prompt of three space characters on a new line: the answer is three and an eighth.
Code:
```   [COEFFICIENTS =: (%. ^/~@:i.@:#) 1 7 23 55 109x   NB. compute coefficients of fitting polynomial
1 3 2 1 0

COEFFICIENTS p. 0.5   NB. evaluate the polynomial at 0.5
3.125

COEFFICIENTS p. i.5  NB. demonstrate polynomial correctness
1 7 23 55 109

_ 1x #: COEFFICIENTS p. 1r2   NB. 3 and 1/8 for amusement.
3 1r8```
Last edited by b49P23TIvg; January 30th, 2014 at 04:45 PM.
6. I would express the algorithm somewhat differently from what you've got. Let's look at your float variable r.
You initialize it in the main program, you decrement r and multiply by r in a recursive function, and you multiply by r back in the main program within a loop. Insane, if not necessarily wrong. Your program does not work. Mine does. The verb np implements the full Newton interpolation scheme for non-uniformly spaced data:
Code:
```   np
aj@:] +/ .* nj

aj
[: , dd/@:|:\@:|:

dd  NB. divided differences
]`(({. - {:)@:[ %~ \$:&}: - \$:&}.)@.(1 < #@:])

assert 1 = 0 1 2 3 dd 0 1 8 27

nj
*/\@:(1 , [: }: (- {.))

DATA
0 1  2  3   4
1 7 23 55 109

1r2 np x: DATA
25r8```
Here's the algorithm:

The Newton polynomial is the dot product of two vectors. (Write a function to compute dot product or use a library version from libatlas.) One of the vectors are the divided difference coefficients aj. The other vector are the products nj.

Construct aj: let x be the vector of the data abscissae, and let y be the corresponding ordinal vector. Compute the divided differences on the prefixes of each vector. Here are the prefixes of abcd:
Code:
```   [\'abcd'
a
ab
abc
abcd```
Consider an agenda of 2 cases. If the length of the input vectors to this divided difference (dd for short) function is 1 then the output is the head of the y vector. Otherwise the result is
Code:
`(dd(behead(x), behead(y))-dd(curtail(x), curtail(y)))/(tail(x)-head(x))`
Construct nj: From the known x subtract the x coordinate of the unknown function value. Compute successive products of the prefixes of these differences. Curtail that vector. Prepend 1.

definitions:
head is first item in a vector.
tail is the last.
behead means to remove the head returning the rest of the list.
curtail means to remove the tail returning the rest of the list.
7. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2013
Posts
34
Rep Power
2
can u suggest corrections in the my algorithm so that it gives correct answer
8. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2013
Posts
34
Rep Power
2
i have done changes in code but still not working the code is
Code:
```#include<stdio.h>
#include<process.h>
int n;
int k=0;
int b[50];
int c[50];
int s[50];
int func(int a)
{
if((a==0)||(a==1))
return 1;
else
return (a*func(a-1));
}
float fun(int b,float g)
{
if((b==0)||(b==1))
return 1;
else
{
g--;
b--;
return g*fun(b,g);
}
}
void recur(int x[])
{
int i;
for(i=0; i<n-1; i++)
c[i]=x[i+1]-x[i];
b[k]=c[0];
if(b[k]!=0)
{
k++;
n--;
recur(c);
}
}
int main()
{
int i;
float p;
int a[50],h;
float r;
float y;
printf("how many values to enter");
scanf("%d",&n);
scanf("%d",&a[0]);
scanf("%d",&a[1]);
for(i=2; i<=n-1; i++)
{
scanf("%d",&a[i]);
if((a[i]-a[i-1])!=(a[i-1]-a[i-2]))
exit(0);
h=a[i]-a[i-1];
}
printf("enter frequencies");
for(i=0; i<n; i++)
scanf("%d",&s[i]);
recur(s);
printf("find which value to find");
scanf("%f",&p);
r=(p-a[0])/h;
i=1;
y=s[0];
while(i<n)
{
y=y+(r*fun(i,r)*b[i-1])/(func(i));
i++;
}
printf("%f",y);
return 0;
}```
9. Maybe this weekend I'll have fun with your algorithm in c. Please note that the recursive scheme I used and outlined to find divided differences is O(n cubed) while an efficient algorithm is O(n squared). I obeyed the rule "First, make one that works.".

Here's a suggestion: your "func" seems to compute factorial (and therefor I guess you're trying to use a Taylor series method). I recommend you name "func" as "factorial".
Last edited by b49P23TIvg; January 31st, 2014 at 07:27 AM.
10. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2013
Posts
34
Rep Power
2
11. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2013
Posts
34
Rep Power
2
i have figured out why there is wrong output.As it is not entering into the second iteration of the while loop

i am unable to rectify this problem
12. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2013
Posts
34
Rep Power
2

#### got the working code

i did some few changes and it is working perfectly.The following is

#include<stdio.h>
#include<process.h>
int n;
int k=0;
float b[50];
float c[50];
float s[50];
float func(float a)
{
if((a==0.0)||(a==1.0))
return 1.0;
else
return (a*func(a-1));
}
float fun(float b,float g)
{
if((b==0.0)||(b==1.0))
return 1;
else
{
g=g-1.0;
b=b-1.0;
return g*fun(b,g);
}
}
void recur(float x[])
{
int i;
for(i=0; i<n-1; i++)
c[i]=x[i+1]-x[i];
b[k]=c[0];
if(b[k]!=0)
{
k++;
n--;
recur(c);
}
}
int main()
{
float j=1.0;
float i;
float p;
float a[50],h;
float r;
float y=0.0;
float z;
printf("how many values to enter");
scanf("%d",&n);
scanf("%f",&a[0]);
scanf("%f",&a[1]);
for(i=2.0; i<=n-1; i++)
{
scanf("%f",&a[i]);
if((a[i]-a[i-1])!=(a[i-1]-a[i-2]))
exit(0);
h=a[i]-a[i-1];
}
printf("enter frequencies");
for(i=0.0; i<n; i++)
scanf("%f",&s[i]);
recur(s);
printf("find which value to find");
scanf("%f",&p);
r=(p-a[0])/h;
do
{
y+=r*fun(j,r)*b[j-1]/func(j);
j++;
}while((b[j-1.0])!=0.0);
z=s[0]+y;
printf("%f",z);
return 0;
}

Thanks for the help.But can u suggest me why the previous code was not working