AlgoPill

Problem Statement: Find the value of a given polynomial P(x) = a₀ + a₁x + a₂x² + a₃x³… a_n-1x^n-1 for a given value of x

Solution: Horner’s rule can be used to solve this problem in O(n) time where n is the maximum power of variable x in the polynomial.

this method works by evaluating the polynomial in a different form which requires reduced number of operations.

P(x) = a₀ + a₁x + a₂x² + a₃x³… a_n-1x^n-1

P(x) = a₀ + x(a₁ + x(a₂ + x(a₃+… +(a_n-2+ xa_n-1)  … )))

The input to this algorithm is an array of co-efficient  in the polynomial, i.e. coeff[i] = a_i, and a number c which is the given value of x at which we have to calculate P(x)

The algorithm maintains a loop invariant which we state below.

Loop Invariant: at the start of the loop the variable result contains a partially calculated polynomial Q_i(x)

Q_i(x) = a_i+1 + a_i+2x + a_i+3x² ….. a_n-1x^n-2-i

Intialization: i=n-1

Q_n-1(x) = 0

Maintenance:

Q_n-2(x) = a_n-1

Q_n-3(x) = a_n-2 + x*a_n-1

Q_i (x) = a_i+1 + a_i+2x + a_i+3x² + …. a_n-1x^n-2-i

Q_i-1(x) = a_i + x*Q_i(x)

= a_i + a_i+1x + a_i+2x² + a_i+3x³ + … a_n-1x^n-1-i

= Q_i-1(x)

Termination:

Q_-1(x) = a₀ + a₁x + a₂x² + …. a_n-1x^{n-2 +1}

Q_-1 (x) = a₀ + a₁x + a₂x² + …. a_n-1x^n-1

which is equivalent to P(c) if we substitute  c for x.

Thus this algorithm correctly calculates