Horner's method evaluates a polynomial at a given point using the minimum possible number of multiplications, by rewriting the polynomial in a nested form so the value is built up through a sequence of multiply-and-add steps working from the highest degree coefficient down to the constant term. This reduces the number of multiplications needed to evaluate an nth degree polynomial from a naive quadratic count to exactly n. Though it bears William George Horner's name from an 1819 paper, the same scheme was described centuries earlier by the Chinese mathematician Qin Jiushao and by Isaac Newton, and it remains a standard technique in numerical computing and computer arithmetic.
Facts
Partially Attested
Credited ToNamed after Horner but described as much older, attributed by Horner to Lagrange and discovered earlier by Chinese and Persian mathematicians Time Complexity
Time Complexity (category) Time Complexity (category)Polynomial Time -- O(n^k) 1 Time ComplexityO(n), n multiplications and n additions for a polynomial of degree n 1 Sources
1. Wikipedia: Horner's method
Lead section, first paragraph
It is named after William George Horner, although it is much older
Lead section, sentence after the nested-form formula
This allows the evaluation of a polynomial of degree n with only n multiplications and n additions.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.