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.

Number Representations

All of the real numbers of a given radix can also be expressed as a polynomial, where the variable is the radix.

For example, in base 10, we can split a number up into its ones, tens, hundreds, and so on. Suppose we have a number n,

$ n = 125 = 1 \times 100 + 2 \times 10 + 5 \times 1 </pre> This is equivalent to a polynomial representation in terms of the radix (10): <pre> n = 125 = 1 \times 10^2 + 2 \times 10^1 + 5 \times 10^0 </pre> This generalizes to larger numbers: <math> n = 3,654,987 = 3 \ times 10^6 + 6 \times 10^5 + 5 \times 10^4 + 4 \times 10^3 + 9 \times 10^2 + 8 \times 10^1 + 7 \times 10^0 $

That's just a polynomial with as many terms as digits, and the unknown $ x $ replacing the base:

$ n = 3 x^6 + 6 x^5 + 5 x^4 + 4 x^3 + 9 x^2 + 8 x + 7 $

It also generalizes to binary numbers or hex numbers:

$ n_{2} = 101010 = 1 \times 2^5 + 1 \times 2^3 + 1 \times 2^1 = 42 $

This number becomes the polynomial:

$ n_{2} = x^5 + x^3 + x $

(where, for binary numbers, the set of possible coefficients is just the set $ {0,1} $.)

Here is a hex number, converted to the equivalent polynomial:

$ n_{16} = BEEF = B \times 16^3 + E \times 16^2 + E \times 16^1 + F \times 16^0 $

Replacing the letters with their decimal equivalents, we get the base 10 equivalent number:

$ 11 \times 16^3 + 14 \times 16^2 + 14 \times 16^1 + 15 \times 16^0 = 48,879 $

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

Programming

Polynomials are a useful

Polynomial/Numerical Recipes - notes from Numerical Recipes on Polynomial and related classes

Polynomial/Numerical Recipes

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.