Horner's method

Horner's method evaluates a polynomial by rewriting it as nested multiplication and addition, reducing the arithmetic operations needed.

Polynomial: An expression formed from constants and variables using addition, subtraction, and nonnegative integer powers. Horner's method applies to polynomials by processing their coefficients in nested form.
William George Horner: An English mathematician known for publishing a practical method for polynomial approximation and root finding. Horner's method takes its name from his 1819 presentation of the procedure.
Polynomial interpolation: The construction of a polynomial that matches specified values at given points. Interpolating polynomials are often evaluated efficiently in nested form.
Direct polynomial evaluation: The evaluation of each polynomial term separately before summing the results. Unlike this term-by-term approach, Horner's method reuses intermediate results.
Polynomial evaluation: The computation of a polynomial's value at a specified input. Horner's method is an efficient procedure for this computation.
Paolo Ruffini: An Italian mathematician who developed methods for polynomial equations and their numerical solution. Ruffini published a closely related procedure before Horner's account.
Synthetic division: A shorthand procedure for dividing a polynomial by a linear factor. Its coefficient recurrence is the same computation used in Horner evaluation.
Estrin's scheme: A polynomial evaluation algorithm that groups terms to expose parallel computations. Estrin's scheme trades additional structure for greater parallelism than Horner's recurrence.
Nested multiplication: A way of expressing a calculation as successively embedded multiplications and additions. This structure is the central transformation that makes Horner's method work.
Isaac Newton: An English mathematician and physicist whose work included numerical methods for solving equations. Newton described a related nested procedure for polynomial approximation.

Linked from 6 pages