Recursively calculate polynomial

[arthurav]

Given the degree of the polynomial and a vector with the polynomial's coefficients is there a more efficient way to recursively calculate the polynomial result for a given x?

This is what i have tried, and it works, but I am asking if there is a more efficient way to do it:

int polynomial(int n,int k,int v[],int x)
{if (k==0){
    int s=0;
    for(int i=0;i<=n;i++)s+=v[i];
    return s;
    }
else 
{for(int i=0;i<=k-1;i++)v[i]*=x;
polinomyal(n,k-1,v,x);}
}

void main()
{
    int n,x,v[10];
    printf("n=");
    scanf("%i",&n);
    for(int i=0;i<=n;i++){
        scanf("%i",&(v[i]));
    }
    printf("x=");
    scanf("%i",&x);
    printf("rezultatul este: %i",polynomial(n,n,v,x));
}

I have tried to find a formula to determine S(n+1) from S(n) and x but have not found anything that way.

[mrnutty]

Why would you do this recursively? It will be better to do it iteratively.
For example :

//assume coefficient is written from highest degree to lowest 
float evaluate(std::vector<float>& coeff, const float x){
 int degree = coeff.size();
 float result = 0.0f;
 for(int i = 0; i != degree; ++i){
   float powResult = std::pow(x,degree - i);
   result += coeff[i] * powResult;
 }
 return result;
}

[tesuji]

Hi,

though your polynomial function calls itself recursively (if we believe that "polinomyal" equals to "polynomial"), yet the value of the polynomial isn't computed recursively instead it is done in for loop if n becomes 0.

You may study this code:

void pore(int d, float a[], float x, float *r){
 if (d>=0){pore(d-1, a, x, r); *r = x**r+a[d];}}

If pore() is called from this context:

// recursively calculated polynomial
//  p(x) = 1*x^3 + 2*x^2 + 3*x^1 + 4*x^0  
int d=3; float a[]={1,2,3,4}, x=2.5, r=0; 
pore(d, a, x, &r);
cout << "polynomial: " << r << endl;

The result is polynomial: 39.625

-- tesu

[Rashakil Fol]

Ignore all these scrub posters and use Horner's algorithm.

[tesuji]

Ignore all these scrub posters and use Horner's algorithm.

Hi Rashakil,

as for Horner you are completely right!

I am already using Horner's first algorithm in this code:

void pore (int d, float a[], float x, float *r){
  if (d>0)pore(d-1,a,x,r); *r=x**r+a[d];}

(I have just somewhat minimized this by dropping two curly brackets what is possible if d>=0 is also replaced by d>0.)

Just consider:

*r=x**r+a[d]

this is very straight Horner's first algorithm. Obviously, you might have ignore this facts accidently.

btw, this very useful scheme should be named after Ruffini because he invited it several years earlier than Horner, therefore all Spanish people call it "Regla de Ruffini".

I am not native English (certainly you have already noticed this), so I would really appreciate you if you could explain the meaning of:

"scrub posters"

to me.

Thank you very much!

-- tesu

[mrnutty]

Ignore all these scrub posters and use Horner's algorithm.

I take that as a compliment, thank you. And thanks for the info.

[tesuji]

Why would you do this recursively? It will be better to do it iteratively.
For example :

//assume coefficient is written from highest degree to lowest 
float evaluate(std::vector<float>& coeff, const float x){
 int degree = coeff.size();
 float result = 0.0f;
 for(int i = 0; i != degree; ++i){
   float powResult = std::pow(x,degree - i);
   result += coeff[i] * powResult;
 }
 return result;
}

Well, firstPerson

your code:

//assume coefficient is written from highest degree to lowest 
float evaluate(std::vector<float>& coeff, const float x){
 int degree = coeff.size();
 float result = 0.0f;
 for(int i = 0; i != degree; ++i){
   float powResult = std::pow(x,degree - i);
   result += coeff[i] * powResult;
 }
 return result;
}

evaluates a polynomial in place x by explicitely computing all x to the power of k, that is: result = coeff[0]*x^degree + coeff[1]*x^(degree-1) +..+coeff[degree] where x^k is given by pow(x,k) method.

Unfortunately, this program code is anything but Horner algorithm.

But you can easily meet Rashakil's stringent requirement for Horner's algorithm by replacing the for-loop and the return statement of your above program code by:

for(int i = 0; i <= degree; i++) result = x*result + coeff[i]; return result;

At this point I am far apart from dubbing persons "scrap posters" as Mr Rashakil did. With regard to the somewhat perceived compliment I can't deny myself to cite a more famous German-American guy: "Only two things are infinite, the universe and human stupidity, and I'm not sure about the former.", as Albert Einstein said before.

-- tesu

[arthurav]

thank you very much. this is just what i was looking for.