Polinômio (Horner)

Horner's scheme: efficient polynomial evaluation

Horner's method rewrites a polynomial in nested form: p(x) = aₙxⁿ + … + a₁x + a₀ = ((aₙx + aₙ₋₁)x + aₙ₋₂)x + …. If you compute each power on its own, you end up doing O(n²) multiplications. Horner cuts that down to O(n), with exactly n multiplications and n additions. The name comes from William Horner (1819), but the trick goes back further, to Liu Hui (~3rd century) and later Newton and Ruffini. To see it in action, take p(x) = 2x³ + 3x² − x + 5 at x = 2 and work from the inside out: ((2·2 + 3)·2 − 1)·2 + 5 = (7·2 − 1)·2 + 5 = 13·2 + 5 = 31.

Applications: numerical analysis and computer algebra

Horner shows up wherever polynomials get evaluated. It's the go-to primitive in numerical analysis, where it accumulates less round-off than the naive form, and it sits under the hood of computer algebra systems like Mathematica, SymPy and Maple. It's also the same recurrence behind synthetic division by x − c (Briot–Ruffini), behind interpolators that evaluate Newton or Lagrange forms, and behind ML inference on polynomial models. Compilers lean on it too, evaluating the Taylor approximations of sin, exp and other transcendentals.

FAQ

How are the coefficients entered? Highest degree first, working down to the constant (aₙ, aₙ₋₁, …, a₀). Any missing term has to go in as a zero.

What is synthetic division? It's Horner applied to x − c. The values you compute along the way turn out to be the quotient's coefficients, and the final one is the remainder p(c).

Is it always faster? When you're evaluating at one point, yes. If you need many points at once, FFT-based methods can come out ahead.

Does it work with complex numbers? Yes. The exact same recurrence carries over to ℂ.