Next: Matrices Up: Horner's Rule for Polynomials Previous: Pseudocode and Playing Computer

Evaluating a polynomial: poly.py

Here is the code, translated into Python, and written as a subprogram with a simple main program for reading the polynomial and testing it:
 ``` #! /usr/local/bin/python3 # Code for evaluating an arbitrary polynomial and its derivative # The polynomial is a[0] + a[1]*x + a[2]*x**2 + \ldots{} + a[n]*x**n # C. DeTar September 10, 2017 # Usage # poly.py # When prompted, enter the degree of the polynomial followed # by the coefficients a[0], a[1], ..., a[n] # Then enter the value of x where you want to evaluate the polynomial # and its derivative import sys ###################################################################### def poly(n, a, x): """Evaluate a polynomial""" p = a[n] for i in range(n): p = a[n-1-i] + x*p return p ###################################################################### def main(): n = eval(input("Degree of polynomial = ")) a = [0 for i in range(n+1)] print("Enter coefficients, a[0], a[1], ..., a[", n, "], one per line") for i in range(n+1): a[i] = eval(input()) x = eval(input("x = ")) p = poly(n,a,x) print("P(", x, ") =", p) ###################################################################### main() ```

Here are the new features of the code:
 ``` a = [0 for i in range(n+1)] ```

This statement creates a list object called `a` and fills it with `n+1` zeros. We will use this list to store the coefficients of the polynomial. We use zero as a placeholder. Later in the code we replace these zeros with the actual coefficients. We can think of the list as a vector and the members of the list as the coefficients of the vector.

Use square brackets around lists, or you can use the built-in Python `list` function, as in
 ``` a = list(0 for i in range(n+1)) ```

Individual members of a list can be accessed with a subscript, as in `a[i]`. Subscripting starts with 0. That is, `a[0]` is the first member in the list. Note that the `range(n+1)` starts at 0 and ends at n, so there are n+1 possible values here. That is how many coefficients there are in a polynomial of degree `n`.
 ``` for i in range(n+1): a[i] = eval(input()) ```

Here we read `n+1` coefficients, one per line and store them in the list `a`.
 ``` for i in range(n): p = a[n-1-i] + x*p ```

The algorithm counts backward from `n-1` to `0`. Here we choose to count forwards, but then calculate the subscript we want to get the effect of counting backwards. So when `i = 0`, we get the coefficient `a[n-1]`, which is the first one we want. When `i = n-1`, the last value in the loop, we get the coefficient `a[0]`, again, the one we want.

Next: Matrices Up: Horner's Rule for Polynomials Previous: Pseudocode and Playing Computer
Carleton DeTar 2017-09-19