Polynomial Evaluation and Synthetic Division Algorithms

The Central Idea

A polynomial

can be evaluated without separately computing every power of \(x\).

By rewriting the polynomial in nested form,

we obtain a simple multiply-add algorithm known as Horner's method.

Ordinary Polynomial Evaluation

Consider

To evaluate at

direct substitution gives

Why an Algorithmic Form Helps

Direct substitution is mathematically correct, but repeatedly computing powers can be unnecessary.

Polynomial evaluation appears inside:

• root-finding algorithms;
• graphing software;
• interpolation;
• simulation;
• optimization;
• computer algebra systems;
• large numerical loops.

A compact evaluation rule becomes valuable when the same operation must be performed many times.

Nested Polynomial Form

Start with

Factor out \(x\) repeatedly:

Continue:

Continue again:

Horner's Method

Horner's method evaluates the nested form one stage at a time.

For coefficients

at \(x=2\):

1. start with \(2\);
2. multiply by \(2\), then add \(-3\);
3. multiply by \(2\), then add \(0\);
4. multiply by \(2\), then add \(5\);
5. multiply by \(2\), then add \(-7\).

Horner Evaluation Step by Step

Begin:

Then

Therefore,

The General Horner Recurrence

For

evaluated at \(x=c\), define

and then work downward:

After the constant term is processed,

Horner's Method as a Table

For

at \(x=2\), the arithmetic can be displayed compactly:

Missing Powers Still Need Coefficients

Consider

The complete coefficient list is

The zeros correspond to the missing \(x^3\) and \(x\) terms.

Omitting those placeholders shifts the entire algorithm and produces an incorrect result.

Example with Missing Terms

Evaluate

at \(x=2\).

Using coefficients

Therefore,

Computational Efficiency

A degree-\(n\) polynomial in Horner form requires approximately

multiplications and

additions.

It also avoids explicitly storing or recomputing

This makes Horner's method especially natural for repeated numerical evaluation.

Direct Evaluation Can Also Be Organized Efficiently

Horner's method is not the only way to evaluate a polynomial in linear computational time.

Powers can also be built incrementally and reused.

Horner's method remains attractive because it uses a particularly compact sequence of multiply-add operations and does not require explicit power values.

What Is Synthetic Division?

Synthetic division is a compact algorithm for dividing a polynomial by a linear divisor of the form

It operates directly on the coefficients rather than writing every power of \(x\) during the arithmetic.

The Structure of Polynomial Division

Dividing \(p(x)\) by \(x-c\) gives

where

is the quotient and \(r\) is a constant remainder because the divisor has degree \(1\).

Example: Divide by \(x-2\)

Divide

by

Include the missing \(x^2\) coefficient:

Since the divisor is \(x-2\), use

Synthetic Division Step by Step

Bring down the leading coefficient:

Multiply by \(2\) and add:

Continue:

Interpreting the Synthetic Row

The resulting numbers are

The first four numbers are quotient coefficients:

The final number is the remainder:

The Division Identity

Therefore,

Expanding the right side recovers the original polynomial.

Horner's Method and Synthetic Division Use the Same Arithmetic

Notice that the synthetic division row

is exactly the same sequence generated by Horner evaluation at

The last value is

which is also the remainder after division by \(x-2\).

The Remainder Theorem

If a polynomial \(p(x)\) is divided by

then the remainder is

Synthetic division therefore performs two jobs at once:

• it computes the quotient coefficients;
• it evaluates the polynomial at \(c\).

The Factor Theorem

If

then the remainder from division by \(x-c\) is zero.

Therefore,

Example: Testing a Factor

Consider

Test whether

is a factor.

Since

use

Synthetic Division by \(x+3\)

Coefficients:

Synthetic steps with \(c=-3\) give

Therefore,

The zero remainder confirms that \(x+3\) is a factor.

Sign Convention Matters

Synthetic division uses the number \(c\) from

Therefore:

while

Using the wrong sign is one of the most common synthetic-division errors.

Synthetic Division with Missing Terms

Divide

by

Use the complete coefficient list:

With \(c=1\), the synthetic row becomes

Interpreting the Missing-Term Example

The quotient is

and the remainder is \(0\).

Therefore,

Repeated Synthetic Division

Synthetic division can be repeated when a factor appears more than once.

Consider

Dividing by

produces a zero remainder and quotient

Testing Multiplicity

Divide the quotient again by

The new quotient is

with remainder \(0\).

Divide once more:

with remainder \(0\).

Therefore,

Synthetic Division as Deflation

Once a root \(c\) is known, dividing by

reduces the degree of the polynomial by one.

This process is often called deflation.

Deflation can simplify the search for additional roots.

Example: Deflating after Finding a Root

Suppose

and we know

Synthetic division by

gives

Therefore,

Continue the Deflation

Factor the quadratic:

Thus,

One known root reduced the remaining problem to a lower-degree polynomial.

Approximate Roots and Deflation

Deflation requires more care when the root is only approximate.

If

rather than \(c=r\) exactly, then synthetic division may leave a small nonzero remainder and slightly perturb the quotient coefficients.

Repeated numerical deflation can accumulate error.

Polynomial Evaluation inside Newton's Method

Newton's method for a polynomial requires repeated evaluation of

and

Horner-style algorithms can make these repeated evaluations efficient.

This is an important example of one numerical algorithm being embedded inside another.

Evaluating a Polynomial and Its Derivative

Extended Horner schemes can compute

and

using related nested recurrences.

The main lesson here is conceptual: polynomial structure can be exploited to avoid unnecessary repeated work.

Evaluation at Many Points

If the same polynomial must be evaluated at many inputs,

Horner's method can be applied independently at each point.

This is common when constructing:

• numerical tables;
• graphs;
• root searches;
• interpolation checks;
• simulation outputs.

Coefficient Representation

Computationally, a polynomial can be stored as a coefficient list:

For example,

becomes

Why Coefficient Lists Are Useful

Coefficient lists make it easy for software to:

• evaluate polynomials;
• perform synthetic division;
• differentiate symbolically;
• add and subtract polynomials;
• compare degrees;
• store missing terms explicitly as zeros.

Horner's Method in Pseudocode

value = leading_coefficient

for each remaining coefficient a
    value = value * x + a

return value

The loop directly mirrors the nested polynomial form.

Example of Horner Pseudocode

For coefficients

and

the running value becomes

The returned value is

Synthetic Division in Pseudocode

bring down the leading coefficient

for each remaining coefficient a
    multiply the previous result by c
    add a
    record the new result

last result = remainder
all earlier results = quotient coefficients

A Programmatic View of Synthetic Division

If the coefficient list is

then the synthetic algorithm generates

The quotient is

and the final value \(r\) is the remainder.

Verification by Reconstruction

After synthetic division, verify the identity

Expanding the right side should reproduce the original polynomial.

This is the strongest direct algebraic check on the quotient and remainder.

Verification by Evaluation

A second check is the Remainder Theorem:

If synthetic division gives remainder \(r\), independently evaluate the polynomial at \(c\).

The two values should match.

Example: Double Verification

For

divided by

synthetic division gives remainder

Direct evaluation also gives

The two methods agree.

Synthetic Division versus Polynomial Long Division

Polynomial long division is general and can divide by higher-degree polynomials.

Standard synthetic division is specialized to divisors of the form

Synthetic division is shorter because the predictable powers and repeated subtraction structure have been compressed into coefficient arithmetic.

When Long Division Is Still Needed

Standard synthetic division does not directly replace long division for a divisor such as

or

More generalized synthetic schemes exist, but ordinary polynomial long division remains the universal elementary method.

Exact Arithmetic versus Floating-Point Arithmetic

With integer or rational coefficients and exact \(c\), synthetic division can often be carried out exactly.

With decimal or floating-point inputs, the running values may contain roundoff error.

This distinction matters when a remainder is expected to be very close to zero.

A Tiny Remainder Is Not Automatically Zero

Suppose numerical synthetic division gives

In floating-point computation, this may represent accumulated roundoff.

Whether it should be treated as effectively zero depends on the scale, precision, and tolerance of the problem.

Scaling and Large Coefficients

Very large or very small coefficients can increase numerical sensitivity.

For example, evaluating

involves quantities on dramatically different scales.

Numerical implementations may need careful scaling and precision control.

Common Error: Forgetting Zero Coefficients

For

do not use

Use

Every power from the highest degree down to the constant term needs a coefficient position.

Common Error: Using the Wrong Synthetic Number

Dividing by

means using

because

Common Error: Treating Every Synthetic Entry as a Quotient Coefficient

The final synthetic value is the remainder.

If a degree-\(4\) polynomial is divided by a linear factor, the quotient has degree \(3\).

Therefore, only the first four synthetic results are quotient coefficients; the fifth is the remainder.

Common Error: Losing the Degree Shift

Dividing a degree-\(n\) polynomial by a nonzero linear factor produces a quotient of degree

The first synthetic result therefore becomes the coefficient of

not \(x^n\).

Common Error: Assuming a Small Remainder Proves an Exact Factor

In exact arithmetic,

proves that \(x-c\) divides the polynomial.

In approximate arithmetic, a small nonzero remainder may indicate a nearby root rather than an exact one.

Interpret the result according to the numerical context.

Common Error: Recomputing Powers Unnecessarily

In repeated numerical evaluation, computing

independently at every step can duplicate work.

Horner's method avoids this by using one running value.

Common Error: Skipping Verification

Synthetic division is compact, which makes transcription mistakes easy to overlook.

Verify using at least one of:

• reconstruction \(p(x)=(x-c)q(x)+r\);
• the Remainder Theorem \(r=p(c)\);
• independent polynomial evaluation.

A Reliable Horner Workflow

1. Write the polynomial in descending powers.
2. Insert zero coefficients for missing powers.
3. Record the coefficient list.
4. Bring down the leading coefficient.
5. Multiply the running value by the input \(c\).
6. Add the next coefficient.
7. Repeat through the constant term.
8. Interpret the final running value as \(p(c)\).

A Reliable Synthetic-Division Workflow

1. Write the divisor as \(x-c\).
2. Use \(c\), including its correct sign.
3. Write the polynomial in descending powers.
4. Insert zero coefficients for missing powers.
5. Bring down the leading coefficient.
6. Multiply by \(c\) and add the next coefficient.
7. Repeat through the constant term.
8. Use all but the final result as quotient coefficients.
9. Interpret the final result as the remainder.
10. Verify with reconstruction or the Remainder Theorem.

Example: Full Horner Workflow

Evaluate

at

Use coefficients

Horner steps:

Therefore,

Verify the Horner Example

Direct substitution gives

This confirms

Example: Full Synthetic-Division Workflow

Divide

by

Use

and coefficients

Complete the Synthetic Division

The synthetic steps produce

Therefore,

and

Thus,

Practice 1: Horner Evaluation

Use Horner's method to evaluate

at

Practice 2: Missing Coefficients

Write the coefficient list for

Practice 3: Synthetic Number

What number should be used in synthetic division for the divisor

Practice 4: Synthetic Division

Divide

by

Practice 5: Remainder Theorem

If synthetic division of \(p(x)\) by

gives remainder \(7\), what is \(p(4)\)?

Practice 6: Factor Test

Suppose

What linear factor is guaranteed by the Factor Theorem?

Practice 7: Quotient Degree

A degree-\(7\) polynomial is divided by a nonzero linear factor.

What is the degree of the quotient?

Practice 8: Repeated Factor

A polynomial divides evenly by \(x-3\), and the quotient also divides evenly by \(x-3\).

What can you conclude about the multiplicity of the root \(x=3\)?

Practice 9: Verify a Remainder

For

find the remainder when dividing by

by evaluating \(p(2)\).

Practice 10: Algorithmic Advantage

State one computational advantage of Horner's method over evaluating every power separately.

Practice Answers

Practice 1

Coefficients:

At \(x=3\):

Therefore,

Practice 2

Include zeros for the missing powers:

Practice 3

Since

use

Practice 4

Use coefficients

with \(c=1\).

The synthetic row is

Therefore,

Practice 5

By the Remainder Theorem,

Practice 6

If

then

is a factor.

Practice 7

Dividing degree \(7\) by degree \(1\) gives quotient degree

Practice 8

The factor \(x-3\) occurs at least twice.

Therefore, \(x=3\) has multiplicity at least

Practice 9

Therefore, the remainder is \(18\).

Practice 10

Horner's method uses a compact sequence of multiply-add steps and avoids separately computing or storing each power of the input.

What to Remember

• Horner's method evaluates a polynomial through nested multiplication and addition.
• Missing powers require zero coefficients.
• A degree-\(n\) Horner evaluation uses approximately \(n\) multiplications and \(n\) additions.
• Standard synthetic division applies to divisors of the form \(x-c\).
• The final synthetic value is the remainder; earlier values are quotient coefficients.
• Horner evaluation and synthetic division use the same underlying multiply-add recurrence.
• The remainder from division by \(x-c\) equals \(p(c)\).
• A zero remainder means \(x-c\) is a factor.
• Repeated synthetic division can expose multiplicity and reduce polynomial degree.
• Verification should use reconstruction, evaluation, or both.

Where We Go Next

Horner's method and synthetic division show how mathematical structure can be translated into efficient computational procedures. The same principle applies when calculations are delegated to calculators, spreadsheets, and computer-algebra systems.

The next lesson, Calculator, Spreadsheet, and Computer-Algebra Methods, examines how numerical and symbolic technologies carry out repeated computation, how results should be interpreted, and how technology can be used without surrendering mathematical verification.