View source for Horner scheme

A method for obtaining the incomplete fraction and the remainder in the division of a polynomial

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h0480301.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>

by a binomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h0480302.png" />, where all the coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h0480303.png" /> lie in a certain field, e.g. in the field of complex numbers. Any polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h0480304.png" /> can be uniquely represented in the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h0480305.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h0480306.png" /> is the incomplete fraction, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h0480307.png" /> is the remainder which, according to the [[Bezout theorem|Bezout theorem]], equals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h0480308.png" />. The coefficients of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h0480309.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h04803010.png" /> are calculated by the recurrence formulas

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h04803011.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>

The following table:''''''<table border="0" cellpadding="0" cellspacing="0" style="background-color:black;"> <tr><td> <table border="0" cellspacing="1" cellpadding="4" style="background-color:black;"> <tbody> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h04803012.png" /></td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h04803013.png" /></td> <td colname="3" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h04803014.png" /></td> <td colname="4" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h04803015.png" /></td> <td colname="5" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h04803016.png" /></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h04803017.png" /></td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h04803018.png" /></td> <td colname="3" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h04803019.png" /></td> <td colname="4" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h04803020.png" /></td> <td colname="5" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h04803021.png" /></td> </tr> </tbody> </table>

</td></tr> </table>

whose upper line is given, while the lower line is filled in accordance with the formulas (2), is used in the computations. In fact, this method is identical with the method of Ch'in Chiu-Shao employed in medieval China. At the beginning of the 19th century it was rediscovered, almost simultaneously, by W.G. Horner [[#References|[1]]] and P. Ruffini [[#References|[1]]].

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  W.G. Horner,   ''Philos. Transact. Roy. Soc. London Ser. A'' , '''1'''  (1819)  pp. 308–335</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  P. Ruffini,   ''Mem. Coronata Soc. Ital. Sci.'' , '''9'''  (1802)  pp. 44–526</TD></TR></table>



====Comments====
Horner's scheme is used for the efficient evaluation of polynomials. The straightforward evaluation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h04803022.png" /> for a given value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h04803023.png" /> by computing the powers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h04803024.png" /> and forming the linear combination according to (1) would require <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h04803025.png" /> multiplications. However, by writing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h04803026.png" /> in the  "nested"  form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h04803027.png" /></td> </tr></table>

only <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h04803028.png" /> (sequential) multiplications are involved. It is easily verified that using this nested representation the work consists of the computation steps given by (2). Since <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h04803029.png" />, the evaluation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h04803030.png" /> requires <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h04803031.png" /> instead of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048030/h04803032.png" /> multiplications.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  F.B. Hildebrand,   "Introduction to numerical analysis" , McGraw-Hill  (1974)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  F. Cajori,   "A history of mathematics" , Chelsea, reprint  (1980)</TD></TR></table>