Horner's method

In <a href="/facts/Mathematics/pxTouaz4">mathematics</a> and <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, Horner's method (or Horner's scheme) is an algorithm for <a href="/facts/Polynomial_evaluation/wWhhHnrL">polynomial evaluation</a>. Although named after <a href="/facts/William_George_Horner/NEXNArjI">William George Horner</a>, this method is much older, as it has been attributed to <a href="/facts/Joseph-Louis_Lagrange/bTQUaSTv">Joseph-Louis Lagrange</a> by Horner himself, and can be traced back many hundreds of years to Chinese and Persian mathematicians. After the introduction of computers, this algorithm became fundamental for computing efficiently with polynomials.
The algorithm is based on Horner's rule, in which a polynomial is written in nested form:

a
                  
                    0
                  
                
                +
                
                  a
                  
                    1
                  
                
                x
                +
                
                  a
                  
                    2
                  
                
                
                  x
                  
                    2
                  
                
                +
                
                  a
                  
                    3
                  
                
                
                  x
                  
                    3
                  
                
                +
                ⋯
                +
                
                  a
                  
                    n
                  
                
                
                  x
                  
                    n
                  
                
              
            
            
              
                =

a
                  
                    0
                  
                
                +
                x
                
                  
                    (
                  
                
                
                  a
                  
                    1
                  
                
                +
                x
                
                  
                    (
                  
                
                
                  a
                  
                    2
                  
                
                +
                x
                
                  
                    (
                  
                
                
                  a
                  
                    3
                  
                
                +
                ⋯
                +
                x
                (
                
                  a
                  
                    n
                    −
                    1
                  
                
                +
                x
                
                
                  a
                  
                    n
                  
                
                )
                ⋯
                
                  
                    )
                  
                
                
                  
                    )
                  
                
                
                  
                    )
                  
                
                .
              
            
          
        
      
    
    {\displaystyle {\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}}}

This allows the evaluation of a <a href="/facts/Polynomial/Lzak8VVx">polynomial</a> of degree n with only 
 
 
 
 n
 
 
 {\displaystyle n}
 
 multiplications and 
 
 
 
 n
 
 
 {\displaystyle n}
 
 additions. This is optimal, since there are polynomials of degree n that cannot be evaluated with fewer arithmetic operations.
Alternatively, Horner's method and Horner–Ruffini method also refers to a method for approximating the roots of polynomials, described by Horner in 1819. It is a variant of the <a href="/facts/Newton%2527s_method/VlRhI2FL">Newton–Raphson method</a> made more efficient for hand calculation by application of Horner's rule. It was widely used until computers came into general use around 1970.

Horner's method open-in-new

Horner's method