Evaluative

What the problem is really saying¶

You are given:

A list of coefficients: a0, a1, a2, …, a8
An integer x

These coefficients define a polynomial:

P(x) = a0 + a1*x + a2*x^2 + a3*x^3 + ... + a8*x^8

Your task: evaluate this polynomial at the given value of x.

Apply it to the example¶

Input coefficients:

1 -2 3 -4 5 -6 7 -8 9

So:

a0 = 1
a1 = -2
a2 = 3
...
a8 = 9

Value of x = 5

The polynomial becomes:

P(5) =
  1
- 2*5
+ 3*5^2
- 4*5^3
+ 5*5^4
- 6*5^5
+ 7*5^6
- 8*5^7
+ 9*5^8

If you compute this directly, term by term, you eventually get:

Which matches the output.

The smart way to compute it (Horner’s Method)¶

The “obvious” way: powers everywhere¶

Suppose you evaluate

P(x) = a0 + a1*x + a2*x^2 + ... + a8*x^8

at x = 5.

A naïve computation looks like this:

x^2 = 5 * 5
x^3 = 5 * 5 * 5
x^4 = 5 * 5 * 5 * 5
...
x^8 = 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5

Now count multiplications:

x² → 1 multiplication
x³ → 2 multiplications
x⁸ → 7 multiplications

Total multiplications just for powers:

1 + 2 + 3 + ... + 7 = 28 multiplications

Then you still have to multiply each power by its coefficient and add everything up.

Also note: numbers like 5^8 = 390625 appear early and hang around. With bigger x or higher degree, those numbers explode fast.

What Horner’s method does instead¶

Horner rewrites the polynomial so that x is used exactly once per term, never as a power.

This:

a0 + a1*x + a2*x^2 + ... + a8*x^8

becomes:

((((((((a8*x + a7)*x + a6)*x + a5)*x + a4)*x + a3)*x + a2)*x + a1)*x + a0

Now look at what the computer actually does.

Step-by-step with real numbers¶

Using your example:

coeffs = [1, -2, 3, -4, 5, -6, 7, -8, 9]
x = 5

Start from the highest coefficient:

result = 9
result = result * 5 + (-8)
result = result * 5 + 7
result = result * 5 + (-6)
result = result * 5 + 5
result = result * 5 + (-4)
result = result * 5 + 3
result = result * 5 + (-2)
result = result * 5 + 1

That’s it.

Now count again (this is the key)¶

One multiplication per coefficient (except the first)
Degree 8 polynomial → 8 multiplications total

Compare:

Naïve method → 28+ multiplications
Horner’s method → 8 multiplications

That’s not a small improvement. It scales brutally well as degree increases.

About “huge intermediate powers”¶

In the naïve method, you explicitly create values like:

x^6, x^7, x^8

Those numbers grow fast and can:

overflow fixed-size integers,
lose precision in floating-point math,
slow down hardware.

In Horner’s method:

you never compute x², x³, x⁴, …
numbers grow gradually
intermediate values stay smaller and more stable

You’re folding the polynomial as you go, not inflating it and hoping for the best.