next up previous
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 up previous
Next: Matrices Up: Horner's Rule for Polynomials Previous: Pseudocode and Playing Computer
Carleton DeTar 2017-09-19