#1
  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<stdio.h>
    #include<process.h>
    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<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<=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("%d",&p);
    r=(p-a[0])/h;
    i=0;
    y=s[0];
    while(i<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. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,851
    Rep Power
    481
    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.

    Comments on this post

    • tendoeschate agrees
    Last edited by b49P23TIvg; January 30th, 2014 at 04:21 PM. Reason: replaced for printf, puts.
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. 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
  6. #4
  7. 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
    please help
  8. #5
  9. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,851
    Rep Power
    481
    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.
    [code]Code tags[/code] are essential for python code and Makefiles!
  10. #6
  11. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,851
    Rep Power
    481
    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.
    [code]Code tags[/code] are essential for python code and Makefiles!
  12. #7
  13. 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
  14. #8
  15. 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;
    }
  16. #9
  17. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,851
    Rep Power
    481
    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.
    [code]Code tags[/code] are essential for python code and Makefiles!
  18. #10
  19. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2013
    Posts
    34
    Rep Power
    2
    please help??
  20. #11
  21. 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
    please help!!
  22. #12
  23. 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

IMN logo majestic logo threadwatch logo seochat tools logo