Polynomials

The fact that the polynomial is an approximation does not necessarily detract from its usefulness because all models are approximations. Essentially, all models are wrong, but some are useful.

- Box and Draper, Empirical Model-Building and Response Surfaces

Mathematics

Polynomials are one of the foundational objects in mathematics, and a keystone of algebra. Polynomials tie together many important concepts, and act as a bridge between the concrete numbers and abstract algebra. It's a great teaching tool, because nearly everybody will know what a polynomial is (or can be taught in 5 minutes), and yet you can spend a lifetime digging into their many useful properties and applications.

Polynomial Interpretation of Radix Representations

All numbers are just polynomials!

$ n = 125 $

$ n = 1 \times 100 + 2 \times 10 + 5 \times 1 $

$ n = 1 \times 10^2 + 2 \times 10^1 + 5 \times 10^0 $

$ n = x^2 + 2 x + 5 $

Polynomials/Numbers - Using polynomials, we can generalize the concept of a radix, understand how we express numbers, and even think about alternative representations of numbers. This page describes some of those ideas.

Algorithms

Define a polynomial as:

$ A(x) = a_0 + a_1 x_1 + a_2 x_2^2 + \dots + a_{n-1} x^{n-1} $

Operations

There are a couple of polynomial operations that will be useful:

• Evaluation of polynomials
• Addition of two polynomials
• Multiplication of two polynomials

Evaluation

To evaluate a polynomial given its coefficients, we can evaluate the polynomial with Horner's Rule:

$ A(x) = a_0 + x(a_1 + x(a_2 + x( \dots ))) $

This is an O(N) algorithm, much faster than evaluating each power of x separately, and adding all the terms together.

Addition

To add two polynomials, $ C(x) = A(x) + B(x) $,

Multiplication

Multiplication is an extremely useful operation - principally because it is equivalent to the convolution operation.

This gets rather complicated rather quickly. There is not an easy way to do this because we have lots of interacting terms. (One constant term, but two linear terms; three quadratic terms; four cubic terms; etc.)

General form: the kth term will be the sum over all the various combinations of coefficients that sum to k

$ c_k = \sum_{j=0}^k a_j b_{k-j} $

Total time to do this? Each term takes linear time (this is like a nested for loop), so the total time is $ O(N^2) $.

"Vanilla" polynomial multiplication therefore takes $ O(N^2) $. But with some care, it can be done in $ O(N \log N) $ time.

Teaching Computer Science with Polynomials

Teaching Inheritance with Polynomials

Notes on teaching concept of inheritance with polynomials: Polynomials/Inheritance

Notes on teaching concept of interface with polynomials: Polynomials/Interface

Polynomials are an interesting test case for inheritance and interfaces:

• Implementing the general (nth degree polynomials) and specific (quadratic/cubic polynomials)
• We learn polynomials in reverse order: from specific to general; but we design code from general to specific.
• Inheritance: parent-child relationship, what the parent has, the child also has, share DNA, can never "escape" that line of heritage
• Interface: club relationship, just pay the dues and meet the requirements and you're in, can go where you like and be who you please, association is ad-hoc

Polynomial Class Testing

Main page: Polynomials/Test Driven Development

You could potentially teach a whole course on test-driven development, and polynomial class is a good simple problem to illustrate some of the principles and motivations for implementing TDD.

• Mechanics of how to write a unit test, how to run a unit test
• Philosophical how, how do you write a unit test?
• Give some examples of numerical recipes style tests - not just one-and-done

What kind of corner cases do you want to try (get fuzzy):

• Very big numbers, very small numbers, very weird numbers
• Hex numbers? Binary numbers? Integers? Nulls?

(Like a very simple fuzzing procedure.)

Polynomial Class Timing

Main page: Polynomials/Timing

Two steps:

• Keep this simple: stick a timer on the front, stick a timer on the end, subtract the two, and there's your time.
• Make it a little more fancy: create your own CSV file, so that you can run it once, open it in Excel, and plot the results.

Take-home lesson:

• Don't let the problem end at the Java code - keep going, use other tools, do more analysis, do more meta-analysis.

Numerical Recipes with Polynomials

Polynomials are great, universally-accessible math objects. They're also commonly used in scientific computing, data analysis and statistics, and in mathematical models, which may need to perform millions or billions of polynomial calculations.

Polynomials/Numerical Recipes - notes from Press et al, Numerical Recipes, and the section on polynomials, rational functions, quadratics, and cubics.

Fitting

To fit an Nth degree polynomial using N+1 points, can use linear algebra.

Here's how it works: an Nth degree polynomial has N+1 coefficients.

Rather than treating x as the unknown, treat a, b, c, d, etc. as the unknowns.

Evaluate the value of the polynomial at the known N+1 points, which gives you an LHS and an RHS - a linear equation. 85 = 2 a + 4 b + 8 c + d

Now do that with all N+1 points, and you get N+1 equations, for the N+1 unknowns. Solve that matrix equation to get the coefficients of your Nth degree polynomial.