AlgoVerse

Horner's rule

Evaluate a degree-n polynomial with only n multiplications and n additions, by factoring x out again and again.

Evaluating a_n·xⁿ + … + a_1·x + a_0 power by power takes O(n²) multiplications (or 2n if each power reuses the last). Horner keeps factoring x out:

Read the full explanation ↓
Input:
coeffs 1×4 · x=3PDF export

P(x) = 2x³ − 6x² + 2x − 1 at x = 3: three multiplications and three additions, giving 5.

  1. def horner(coeffs, x):
  2. # coeffs holds one row: a_n, …, a_1, a_0 (the highest power first).
  3. y = 0
  4. rows = []
  5. for a in coeffs[0]:
  6. y = y * x + a
  7. rows.append((a, y))
  8. return y

Invariant: After k coefficients, y is the value of the polynomial made of just those k highest coefficients (with lowered powers).

Start

y—

The table is still empty.

Local variables

x3

Orange = changed in this step

coeffs list

[2, -6, 2, -1]

Call stack

  1. horner()line 1
Step 1 of 17
Black = step · Orange = key stepstep: 0/4
    Explanation

    The idea

    Evaluating a_n·xⁿ + … + a_1·x + a_0 power by power takes O(n²) multiplications (or 2n if each power reuses the last). Horner keeps factoring x out:

    2x³ − 6x² + 2x − 1  =  ((2·x − 6)·x + 2)·x − 1

    so only n multiplications and n additions are needed.

    Uses

    • Converting a number from any base to decimal (the "reading a binary number" input).
    • Dividing a polynomial by x − c (synthetic division): the intermediate values of y are the quotient's coefficients.

    What to watch in the trace

    • Each table row is one coefficient and the value of y after it.