Horner's algorithm gives us the most efficient polynomial evaluation method. With the algorithm, evaluation of a n-degree polynomial requires n products and n sums. This is clearly much less expensive than a brute computation with powers.
*[NMC]
Python Implementation Attempt
#Variable Initialization#Retrieve polynomial degree from usern = int(input("Poly. Degree:"))#Initialize list to store coefficient values and polynomial termscoeff = [None for x in range(n+1)]poly = [None for x in range(n+1)]print("Please enter poly. coefficients:")#Populate coefficient array with user inputfor i in range(0,int(n)+1): coeff[i] = input("Degree {0} coeff: ".format(i)) coeff[i] = float(coeff[i]) #Poly list created to store polynomial terms poly[i]= str(coeff[i]) + "x^{0}".format(i)print("Entered Polynomial: ", *poly)#Request point for evaluationx = float(input("x = "))#Evalute p(x), call the evaluation p, by Horner's algorithm (!)p = coeff[n]for j in range(1-n, 1): p = coeff[abs(j)] + x*pprint("P({0}) = {1} (Horner Algorithm)".format(x,p))#Evaluate p(x) by brute multiplicationp = 0for i in range(0,n+1): p = p + coeff[i]*x**iprint("P({0}) = {1} (Brute Multiplication)".format(x,p))Note: b_(-1) corresponds to p(r)
We can combine the use of Horner's algorithm in evaluating polynomials and carrying out synthetic division to.... determine the coefficients of the Taylor series expansion of a polynomial centered at any point, c. This is Horner's "complete" algorithm. Because of the fact that the polynomial is both evaluated at c, and the linear term (x-c) is factored out of the polynomial in each step (both involve the same value c), the two applications of Horner's algorithm can be done in a single nested for loop. The pseudocode is included in the image below:
Python Implementation Attempt
#This program will take a polynomial written in standard form and #determine the coefficients of the Taylor series expansion of the polynomial #evaluated at some center, c. #Variable Initialization#Retrieve polynomial degree from usern = int(input("Poly. Degree:"))#Initialize list to store coefficient values and polynomial termscoeff = [0 for x in range(n+1)]poly = [0 for x in range(n+1)]Tay_coeff = [0 for x in range(n+1)]Tay_poly = [0 for x in range(n+1)]print("Please enter poly. coefficients:")#Populate coefficient array with user inputcorrect = Falsewhile correct == False: for i in range(0,n+1): coeff[i] = input("Degree {0} coeff: ".format(i)) coeff[i] = float(coeff[i]) #Poly list created to store polynomial terms poly[i]= str(coeff[i]) + "x^{0}".format(i) if i < n: poly[i] += " +" print("Entered Polynomial: ", *poly) correct = bool(input("Is this the polynomial you owuld like to expand?")) #Request point for Taylor Series Expansionc = float(input("c = "))#Begin implementation of complete Horner's Algorithm.Tay_coeff = coeffprint("**")print(Tay_coeff)print(coeff)for k in range(0,n): for j in range(n-1,k-1,-1): Tay_coeff[j]=Tay_coeff[j] + (c * Tay_coeff[j+1])for i in range(0,n+1): Tay_poly[i]= str(Tay_coeff[i]) + "(x-{0})^{1}".format(c,i) if i < n: Tay_poly[i] += " +" print(*Tay_poly)Polynomial deflation is the removal of a linear factor from a polynomial. This is a specific example of polynomial long-division in which one has a linear divisor with unit leading coefficient. Horner's algorithm (also called "synthetic division") can be used in this special linear case of polynomial long-division. A thorough run down on synthetic division can be found here.
In considering the step-by-step process of synthetic division, you will notice that the overall structure involves the nested multiplication that led to the use of Horner's algorithm in the algorithm evaluation problem. We start with a value, multiply it by r, add that to some other value, multiply the whole thing by r and add that to the next value, and so on...
The pseudocode of Horner's algorithm applied to carry out synthetic division is shown below.
Horner's algorithm is a nice, general algorithm for evaluating a nested sequence of sums and products of the canonical form given by the nested polynomial expression.