Calculus×Computing
ES

Polynomial functions

Level FundamentalDifficulty ★★★★★Concept⌖ Open in the map

What is it?

p(x)=anxn+⋯+a1x+a0p(x) = a_n x^n + \dots + a_1 x + a_0. Computed with additions and multiplications only, they are what a processor evaluates best — and other functions are approximated by them (Taylor, interpolation).

Formulas

p(x)=a0+x(a1+x(a2+⋯+x an))p(x) = a_0 + x\big(a_1 + x(a_2 + \dots + x\,a_n)\big)
Horner's rule: nn multiplications

Where it shows up in computing

  • Bézier curves and splines★★★★★fundamentalComputer graphics

    Bézier curves and splines are polynomial pieces written in the Bernstein basis.

  • Algorithm analysis and complexity★★★★★frequentScientific computing and algorithms

    "Polynomial time" O(nk)O(n^k) is the dividing line between tractable and intractable problems (P).

  • Elliptic curve cryptography★★★★★indirectCryptography and security

    The curve is the zero set of the polynomial y2−x3−ax−by^2 - x^3 - ax - b, but over a finite field, where calculus does not apply.

Where is it used?

Computing topics reachable from here, through the chain of ideas that leads to them:

λ Scientific computing and algorithms

ℒ AI and machine learning

3D Computer graphics

⚛ Physics and simulation

∿ Signals, media and vision

⚙ Robotics and control

⇄ Optimization and systems

⊕ Cryptography and security

ψ Quantum computing and physics

What depends on it

Exercises

1Computing

How many multiplications does evaluating p(x)=3x4−2x3+x−7p(x) = 3x^4 - 2x^3 + x - 7 take naively, and with Horner?

Solution

Naively 4+3+1=84 + 3 + 1 = 8 (computing each power from scratch). Horner: ((3x−2)x+0)x+1)x−7((3x - 2)x + 0)x + 1)x - 7, 4 multiplications.

This page has the essentials. A fuller treatment (intuition, formal definition, worked example) is on the way.

↑ ↓ to navigate · ↵ · Esc