Polynomials

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.

Python for Radix Conversions

Note that the radix conversions above (some non-decimal base into decimal base) are straightforward to do with Python - when you create an integer object, you can pass a string containing the number, then pass a second argument that specifies the radix:

$ python

>>> int('101010',2)
42

>>> int('BEEF',16)
48879

>>> int('DEADBEEF',16)
3735928559

Computer Science and Programming

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

Implementing a Polynomial Class

Polynomials/Java - Covering some notes on implementing Polynomial class in Java.

To better understand the implementation, its advantages and disadvantages, and its performance, we need to implement two bits of functionality, we need to implement two things: testing and timing.

• Testing allows to check the method is implemented correctly, and quantify the numerical accuracy.
• Timing allows to test the performance of each method and quantify its speed.

Polynomial Class Testing

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, very simple fuzzing procedure.)

Polynomial Class 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.

Polynomials/Inheritance - teaching inheritance and interfaces with polynomials and their related families

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.