horner's rule C++

Question

While trying to evaulate polynomials using Horner's Rule I have a sample code segment like so:

int Horner( int a[], int n, int x )
{
    int result = a[n];
    for(int i=n-1; i >= 0 ; --i)
        result = result * x + a[i];
    return result;
}

I understand that a is an array of coefficients and that x is the value that I would like to evaluate at. My question is what is the n for?

Answer 1

n is the size of the array

Answer 2

'n' is index of the last element in the array. Therefore, n is one less than the size of the array.

Answer 3

The code appears to be incorrect. The statement:

int result = a[n];

should fail if n is size of the array... If n is the size of the array minus 1, then it will work but the contract of the function is very strange in this case. It is impossible to pass empty array to the function, which is not generic and requires additional checking on caller's side.

Answer 4

In C++, the language does not provide native support for getting the length of an array. Because of that, code must often maintain a separate variable that holds the length. In this example, the n parameter tells the Horner function how many elements are in the array.

In C++ it's idiomatic to pass the number of elements. Since arrays are 0 based, the last element of the array is arr[n-1].

Answer 5

Horner's rule is based on a substitution series representing a polynomial.

In your implementation above, n represents the number of iterative substitutions (the length of the array of coeffecients)

Because there is no quick way to find the length of an array in c++ (eg. in C# you can do a.Length), you pass the length of the a[] as a parameter to the function.

So n has no real direct relevance to Horner's rule in this context - its an implementation detail of the algorithm

Answer 6

n is the degree of the polynome (and a polynome of degree n, aside from 0 which is kind of special, has n+1 coefficients, so size of array = n+1, n = size of array - 1)