Fastest way of evaluating a polynomial at a particular value

What is the fastest known algorithm for evaluating a polynomial of a given degree, and known coefficients(in order)? I tried to do it the following way:

long long int evaluatepoly(long long int* coeffa0,long long int degree,long long int x)
{
/*coeffa0 is the coeffecient array in order x^0,x^1,x^2....degree->degree of polynomial
  and x is the value where the polynomial is to be evaluated*/
  if(degree==1)
  {
    return (coeffa0[0] + (coeffa0[1])*x);
  }
  else if(degree==0)
    return coeffa0[0];
  else{
    long long int odd,even,n=degree;
    if(degree%2==0){
      odd=(n/2);
      even=(n/2)+1;
    }
    else{
      odd=(n+1)/2;
      even=(n+1)/2;
    }
    long long int oddcoeff[odd],evencoeff[even];
    int i=0;
    while(i<=degree)
    {
      if(i%2==0)
        evencoeff[i/2]=coeffa0[i];
      else
        oddcoeff[i/2]=coeffa0[i];
      i++;
    }
    int y=x*x;
    return (evaluatepoly(evencoeff,(even-1),y) + x*(evaluatepoly(oddcoeff,(odd-1),y)));
  }
}

I am a beginner so recommendations in improving the above code is also welcome(in C/C++).

Your evaluation has recursive complexity

T(2n)=2*T(n)+2

if counting only multiplications, plus some overhead for the construction of the sub-arrays, resulting in overall T(n)=2n-2 multiplications (for n power of 2).

The (misnamed) Horner method uses n-1 multiplications.