3.5. JNB Lab: Introduction to Python#
This lab accompanies the chapter “Introduction to Python.” The goal of this lab is to discover a sampling of Python features and programming concepts by way of example. The concepts covered in this lab are
Recursive algorithms
Python list comprehensions
Optimization by way of mathematical transformation
Programming as data plus operations
Classes
The running example on which we hang these concepts is modeling a polynomial function, that is, a function in the form of
for example, \(f(x) = 3 + 4x - 7x^2 + 5x^3\).
In the chapter itself, we suggested that a function like this can be represented by a list of coefficients—in this case, [3.0, 4.0, -7.0, 5.0]. Think for a moment about this idea of representation: We have taken the essential information from the abstract concept of a polynomial function and reduced it to a form such that that information can be stored in a Python type. The number of terms—the degree of the polynomial—can be determined by the length of the list, and each coefficient’s position in the list indicates the power of \(x\) that the coefficient corresponds to. If there is any power of \(x\) for which this polynomial doesn’t have a term, we can represent that with a 0.0 in the corresponding position in the list. But it this list doesn’t act like a function—you cannot apply it to a specific value of \(x\). Instead, we need to have separate Python functions to compute anything about this polynomial function.
In the section we saw the following function for evaluating a polynomial represented as a list of coefficients
def evaluate_polynomial(coefficients, x) :
result = 0
for i in range(len(coefficients)) :
result += coefficients[i] * x**i
return result
This lab steps you through variations on this function.
3.5.1. Doing it recursively#
Recursion is defining something in terms of a smaller version of itself. Many things in both math and computation afford simple self-referential definitions. The trick is to identify a part that is similar to a whole. Consider polynomials—notice that in our example, the terms \(3 + 4x - 7x^2\) by themselves make a polynomial. Suppose we define \(g(x) = 3 + 4x - 7x^2\), then our original function \(f\) can be rewritten as
…that is, a (smaller) polynomial plus the term of degree 3. In general, a polynomial of degree \(n \geq 0\) is
For a given list, such as one storing the coefficients of a polynomial, we can grab all but the last element using slicing and negative indexing:
coeffs = [3.0, 4.0, -7.0, 5.0]
print(coeffs)
print(coeffs[:-1])
(Notice that the degree of the polynomial and the length of the list representing the polynomial are not equal. Rather, the length of the list, or the number of coefficients, is one greater than the degree. A zero-degree polynomial has one coefficient, namely the constant term; a list representing a zero-degree polynomial has length one, since it contains only that constant. Moreover, the degree of the polynomial is a valid index into the list of coefficients, since a polynomial of degree \(n\) has an \(n\)th coefficient.)
Thus we have a conceptual way to evaluate a polynomial in terms of evaluating a smaller polynomial,
and we know how to extract a smaller polynomial from one given as a list. We have the makings of a recursive process for polynomial evaluation. What we still need is a sense of how to make a recursive function in code.
Let’s pause this problem and try a simpler one: Suppose we want to compute the result of multiplying
all the elements in a list together, which we might call the product of a list. Python has a built-in function sum which takes a list and computes the sum of all the elements in that list, but it doesn’t have a similar built-in product function for lists. We’ll need to write it ourselves. But notice that the product of all the elements in a list is equal to the product of all but the last element followed by multiplying that last element with the product of the rest. What we need to check for is whether the list is empty, in which case the list elements have a default product of 1.
def product(xx) :
if len(xx) == 0:
return 1
else :
return product(xx[:-1]) * xx[-1]
product([2, 4, 3, 9])
We call the special case where we can find the answer directly the base case, and the case where the function calls itself the recursive case. To follow how this works, inspect this revision that includes tracing code so that we can follow how the function executes.
def product(xx, original_length) :
indent = ' ' * (original_length-len(xx))
print(indent + "product called with " + str(xx))
if len(xx) == 0:
result = 1
else :
result = product(xx[:-1], original_length) * xx[-1]
print(indent + "returning with result " + str(result))
return result
product([2, 4, 3, 9], 4)
However, this “traced” version is just to build your intuition (and faith) about how recursion works. This is not the mental model you should have when thinking about recursive algorithms. Instead, your attention should be on \(f(x) = \hat{f}(x) + c_n x^n\), that is, how to relate a (bigger) problem in terms of a (smaller) problem.
Exercises#
1.1
Write a new version of the Python function evaluate_polynomial that does not use a while loop but instead uses recursion. A stub for this function is given below. You may assume that the minimum size of the list is 1, which is checked by an assertion in the stub:
def evaluate_polynomial(coefficients, x) :
assert len(coefficients) > 0
# Add code here
1.2
In the function product, why is the product of an empty list 1 instead of 0?
3.5.2. Doing it by comprehension#
Although recursion is a useful tool of abstraction that allows us to simplify many algorithmic tasks, neither the recursive version nor the original iterative (i.e., “using a loop”) version of evaluate_polynomial follows the native Python idiom for identifying patterns that can be expressed compactly, like what we have in the mathematical formula for a polynomial. For that, we need to use a Python construct called a list comprehension, which allows us to make a new list using a pattern.
Python comprehensions are modeled after mathematical notation used to specify a sequence. Consider the sequence of powers of two:
In this we’re considering the first item in the sequence to be \(2^0 = 1\), which plays well with zero-based indexing. Now, instead of listing the elements in the sequence, we can specify this sequence using a pattern:
where \(\mathbb{W}\) stands for whole numbers, that is, non-negative integers. This is an infinite sequence, but we can specify a finite portion of it by setting an upper bound for \(i\). We let \(\mathbb{Z}_n\) stand for nonnegative integers less than \(n\), for example \(\mathbb{Z}_5 = \{ 0, 1, 2, 3, 4 \}\). Now we can say
We express the same idea in Python:
[2**i for i in range(8)]
So far we have seen how to produce the items in a sequence using a comprehension. It is only one step further to turn this into a summation: Use the built-in Python function sum alluded to above.
sum([2**i for i in range(8)])
Turning back to our running example, we notice that the terms in a polynomial are just the elements in a sequence specified by the pattern \(c_i x^i\) for \(i \in \mathbb{Z}_{n+1}\) where \(n\) is the degree of the polynomial.
Exercises#
2.1
Write new version of the Python function evaluate_polynomial that uses neither loop nor recursion
but instead uses sum and a list comprehension. A stub for this function is given below. As before, you may assume that the minimum size of the list is 1.
def evaluate_polynomial(coefficients, x) :
assert len(coefficients) > 0
# Add code here
2.2
When we specified the terms of a polynomial by a pattern, why did we say “for \(i \in \mathbb{Z}_{n+1}\)” instead of “for \(i \in \mathbb{Z}_{n}\)”?
3.5.3. Doing it efficiently: Horner’s rule#
In the section “Thinking through Algorithms”, we considered not only what an algorithm does, but how efficiently it does it, which we measured by counting how many steps the algorithm took in terms of the size of the input. We can measure the computational cost of these algorithms for evaluating a polynomial by counting the number of multiplications, which we’ll use as a proxy for the entire cost.
For the \(i\)th term, \(c_i x^i\), we perform \(i\) multiplications. For example, \(3 x^4 = 3 \cdot x \cdot x \cdot x \cdot x\). This means that in terms of the degree of the polynomial \(n\), the number of multiplications is an arithmetic sum, \(0 + 1 + 2 + \cdots n\), which is quadratic in \(n\):
All of our solutions so far have the same cost by this measure, because they all perform the same multiplications.
(This is assuming that the Python ** operator simply does a sequence of multiplications—which is not true but is still a reasonable model for our present purposes.)
But, one might suppose, aren’t those multiplications inherent to the problem? Surely we can’t reduce that cost?
In fact, we can write an algorithm for evaluating polynomials that performs fewer multiplications, and the first insight into how is to notice that our algorithms so far have all done redundant work when computing the powers of \(x\). For example, if one of our algorithms needs to compute \(x^4\), it does it from scratch. However, on a previous step they had already computed \(x^3\), prior work that the algorithm fails to capitalize on.
We can rewrite our original, iterative version so that it saves its exponentiation work from the previous iteration and eliminate this unnecessary work:
def evaluate_polynomial(coefficients, x) :
result = 0
x_pow = 1 # This is always x^i; it's the power of x for the next iterations
for i in range(len(coefficients)) :
result += coefficients[i] * x_pow
x_pow *= x
return result
But there is also a way we can manipulate the formula algebraically to achieve this. We repeatedly pull out a factor of \(x\) from portions of the polynomial:
This formula is known as Horner’s Rule.
Exercises
3.1
Finish the following Python function to implement evaluate_polynomial using Horner’s Rule iteratively. Notice that the loop in the given code counts down from \(n\) using variable i. For each step in the process, we execute a piece of the formula in the form of
def evaluate_polynomial(coefficients, x) :
result = 0
for i in reversed(range(len(coefficients))) :
# add code here
return result
3.2
Write another version of evaluate_polynomial that uses Horner’s rule recursively. To catch the recursive structure of this problem, look again at the first step that we took when factoring:
Notice that \(c_1 + c_2 x + c_3 x^2+ \cdots c_{n-1} x^{n-2} + c_n x^{n-1}\) is itself a polynomial. It has degree \(n-1\). We can retrieve that (sub-)polynomial from a list that represents the larger polynomial, grab the slice beginning at index 1. As before, we provide a stub:
def evaluate_polynomial(coefficients, x) :
assert len(coefficients) > 0
# add code here
3.3
How many multiplications does Horner’s rule perform when given a polynomial with degree \(n\)?
3.5.4. Making other operations (requires calculus)#
Programming is about representing information and making operations to, well, operate on that information. We have been using a list of coefficients to represent information about polynomials, and we have one operation that we have implemented several ways. However, evaluating mathematical functions is not the only thing we ever want to do with them. From calculus, we know that we can also differentiate or integrate a function. Remember that for a polynomial in the form we have been using, its derivative is
The indefinite integral (or antiderivative) is (with arbitrary constant \(c^\ast\))
The definite integral from \(a\) to \(b\) is
Using this refresher, we proceed directly to the…
Exercises#
4.1
Finish the following Python function to compute the derivative of a given polynomial, represented as a list of coefficients. Notice that this function should return another polynomial, represented as a list. Use a list comprehension to do this.
def differentiate_polynomial(coefficients) :
# add code here
4.2
Finish the following Python function to compute the indefinite integral of a given polynomial, represented as a list of coefficients. Like the previous problem, this function should return another polynomial. Use a list comprehension.
def integrate_polynomial_indef(coefficients) :
# add code here
4.3
Finish the following Python function to compute the definite integral of a given polynomial with lower and upper bounds. The function you write for this exercise should call your function from the previous exercise.
def integrate_polynomial_def(coefficients, a, b) :
# add code here
3.5.5. Making a class#
Programming is about representing information and making operations on that information. What makes a class different from other types or programming modules is that it allows us to package information and the operations on the information into one encapsulated entity. Consider the following class for representing polynomials which wraps a list of coefficients together with the operation to evaluate that polynomial (we used the iterative Horner’s rule version). We don’t put that functionality into a method called evaluate_poly but instead into a special method called __call__. This name gets special recognition in Python, making the class callable. That means that instances of this class can be used as functions, which makes sense in this case because polynomials are mathematical functions.
class Polynomial :
def __init__(self, coeffs) :
self.coefficients = coeffs.copy()
def __call__(self, x) :
result = 0
x_pow = 1 # This is always x^i; it's the power of x for the next iterations
for i in range(len(self.coefficients)) :
result += self.coefficients[i] * x_pow
x_pow *= x
return result
def degree(self) :
return len(self.coefficients)-1
# Another special function, this one makes a nice string representation
# of the object
def __str__(self) :
if len(self.coefficients) == 0 :
return '0.0'
else :
to_return = str(self.coefficients[0])
for i in range(1, len(self.coefficients)) :
to_return += ' + ' + str(self.coefficients[i]) + 'x'
if i > 1 :
to_return += '^' + str(i)
return to_return
# The next three are for the exercises
def differentiate(self) :
pass
def integrate_indef(self) :
pass
def integrate_def(self, a, b) :
pass
Let’s demonstrate how a callable can be used.
f = Polynomial([3.0, 4.0, -7.0, 5.0])
print(f)
f(2.5)
Exercises#
5.1
Finish the class Polynomial. You can reuse code from previous exercises, adjusting them
to make sense in the context of the class. The methods differentiate and integrate_indef should return Polynomials.