Horner's rule

English[edit]

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

(mathematics, computing theory) The rule stating that a polynomial of degree n can be (optimally) evaluated with only n multiplications and n additions: ${\begin{aligned}a_{0}&+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}\\&=a_{0}+x{\bigg (}a_{1}+x{\Big (}a_{2}+x{\big (}a_{3}+\cdots +x(a_{n-1}+x\,a_{n})\cdots {\big )}{\Big )}{\bigg )}.\end{aligned}}$