Evaluating a polynomial and Horner's Rule

Given the polynomial

where  are real numbers, we wish to evaluate the polynomial i.e. find it's value at a given value of x, say x₀. This value represents the value of p(x), which can be any function under analysis at the point x₀ in space.

INPUT :

1. The value of x₀
2. The values of the coefficients a₀...a_n

OUTPUT :

The value of the polynomial at x.


THE "NAIVE" METHOD :

The most basic and preliminary method would be to separately evaluate each term in the expression and then successively add all the terms (monomials). Let us consider p(x) to be a polynomial of degree n. It, then contains, at the most, n+1 terms (from degree 0 to n). The naive method, then, requires at the most n additions to add those n+1 terms. In fact, these n additions are absolutely necessary for any algorithm used.

Now lets consider the number of multiplications involved. An n-degree polynomial will have at the most n co-efficients. We need to perform 1 multiplication for each, giving us a total of n multiplications. This factor, too, is independent of the algorithm chosen. Additionally, when we calculate the powers of x, we multiply x by itself each time to get a higher power (we consider a machine where power calculation is NOT O(1), i.e. it cannot be performed in a single step, which is true in most cases). Therefore, to get xⁿ, we need to perform n multiplications. Therefore, maximum total number of multiplications for power will be:
                                                      ∑(i=0 to n-1) {i} = n(n-1)/2
i.e. (n²- n)/2 multiplications. But we can avoid the need to multiply n times to get xⁿ. We can use iterative methods to increase the efficiency, because xⁿ is x*x^n-1 and so on. Thus, by using iterative functions, we need only (n-1) multiplications.
Therefore, in the basic method, we need a total of n additions and (n²-n)/2 + n i.e. (n²+n)/2 multiplications, giving O(n²). However, in the iterative method, we need n - 1 + n = 2n - 1 multiplications along with n additions, still giving O(n). Can we do any better?

HORNER'S ALGORITHM :

Horner's algorithm provides a way of evaluating any polynomial in ϴ(n). It is just another way of representing every polynomial by iteratively multiplying the variable 'x' to a shorter sequence. Horner's method can be represented as follows:


The algorithm for Horner's method is pretty straightforward:

1.  y = 0                                         ϴ(1) 1 time
2.  for i = n downto 0                       ϴ(1) n+1 times
3. y = ai + x*y                                ϴ(1)                                     n times

Thus, the algorithm takes ϴ(n) which is way better than the naive method. Also, Horner's method takes n additions and n multiplications as can be seen from the algorithm above. Thus, it is more efficient i terms of space as well.

Horner's algorithm can be extended to find the "approximate roots" of the equation. If the Horner's equation above is observed, we find that each pair of parantheses enclose 1 polynomial smaller than p(x). Thus we can "break down" any given polynomial into smaller polynomials by dividing it by a given factor and subtracting it from a constant term. The constant term, thus becomes, the remainder and the constant factor, the divisor. For example,
                  x³ - 6x² + 11x - 6 can be represented in Horner's form as -6 + x (11 + x (-6 + x (1)))
When x-1 = 0; x = 1. This implies, that if we divide the above polynomial by (x-1), we can consider 1 to be a value of x. The above polynomial can, thus, be divided by (x-1) (here, the constant factor and divisor is 1) to get the quotient x² - 5x + 6 and remainder 0. This leads us to a very important format in Mathematics and in Computer Science: The Synthetic Division.

 x₀│   x³    x²    x¹    x⁰
 3 │   2    −6     2    −1
   │         6     0     6    
   └────────────────────────
       2     0     2     5

Notice the similarity between the algorithm mentioned above and the synthetic division performed here. The coefficient of x³ which is equivalent to a_n for n = 3 is directly copied and the later coefficients (a_n-1 to a₀) are multiplied by the value of x(i.e.3) to get the coefficients of a smaller polynomial (2x² + 0x + 2) and remainder 5. Thus, we see that by mere manipulation of coefficients as in the Horner's rule, we can not only evaluate any polynomial, but can also calculate the approximate roots of the same.