Horner's rule

English

Named after William George Horner, though it significantly pre-dates his work.

Template:Lb The rule stating that a polynomial of degree n can be (optimally) evaluated with only n multiplications and n additions: $\begin{matrix} a_{0} & + a_{1} x + a_{2} x^{2} + a_{3} x^{3} + \dots + a_{n} x^{n} \\ = a_{0} + x (a_{1} + x (a_{2} + x (a_{3} + \dots + x (a_{n - 1} + x a_{n}) \dots))) . \end{matrix}$