Horner's method


In mathematics, Horner's rule is a method for approximating the roots of polynomials that was described by William George Horner in 1819. It gave a convenient way for implementing the Newton–Raphson method for polynomials that was suitable for efficient hand calculation and was widely used until computers came into general use in about 1970.
One aspect of this method was the use of synthetic division for implementing polynomial long division, and some elementary level texts use Horner's method as yet another name for this ancient trick which Horner ascribed to Joseph-Louis Lagrange but which can be traced back many hundreds of years to Chinese and Persian mathematicians.
After the introduction of computers Horner's root-finding method went out of use and as a result the term Horner's method has often been used to mean just the algorithm for polynomial evaluation that underlies synthetic division.
The key idea behind this is the identity:
This allows evaluation of a polynomial of degree with only multiplications and additions. This is optimal, since there are polynomials of degree that cannot be evaluated with fewer arithmetic operations

Polynomial evaluation and long division

Given the polynomial
where are constant coefficients, the problem is to evaluate the polynomial at a specific value of
For this, a new sequence of constants is defined recursively as follows:
Then is the value of.
To see why this works, the polynomial can be written in the form
Thus, by iteratively substituting the into the expression,
Now, it can be proven that;
This expression constitutes Horner's practical application, as it offers a very quick way of determining the outcome of;
with b0 being the division's remainder, as is demonstrated by the examples below. if x0 is a root of p, then b0 = 0, which means you can factor p with.
As to finding the consecutive b-values, you start with determining bn, which is simply equal to an. You then work your way down to the other b's, using the formula;
till you arrive at b0.

Examples

Evaluate for
We use synthetic division as follows:
x0│ x3 x2 x1 x0
3 │ 2 −6 2 −1
│ 6 0 6
└────────────────────────
2 0 2 5
The entries in the third row are the sum of those in the first two. Each entry in the second row is the product of the x-value with the third-row entry immediately to the left. The entries in the first row are the coefficients of the polynomial to be evaluated. Then the remainder of on division by is 5.
But by the polynomial remainder theorem, we know that the remainder is. Thus
In this example, if we can see that, the entries in the third row. So, synthetic division is based on Horner's method.
As a consequence of the polynomial remainder theorem, the entries in the third row are the coefficients of the second-degree polynomial, the quotient of on division by.
The remainder is 5. This makes Horner's method useful for polynomial long division.
Divide by :
2 │ 1 −6 11 −6
│ 2 −8 6
└────────────────────────
1 −4 3 0
The quotient is.
Let and. Divide by using Horner's method.
0.5 │ 4 -6 0 3 -5
│ 2 -2 -1 1
└───────────────────────
2 -2 -1 1 -2
The third row is the sum of the first two rows, divided by 2. Each entry in the second row is the product of 1 with the third-row entry to the left. The answer is

Efficiency

Evaluation using the monomial form of a degree-n polynomial requires at most n additions and /2 multiplications, if powers are calculated by repeated multiplication and each monomial is evaluated individually. If numerical data are represented in terms of digits, then the naive algorithm also entails storing approximately 2n times the number of bits of x. By contrast, Horner's method requires only n additions and n multiplications, and its storage requirements are only n times the number of bits of x. Alternatively, Horner's method can be computed with n fused multiply–adds. Horner's method can also be extended to evaluate the first k derivatives of the polynomial with kn additions and multiplications.
Horner's method is optimal, in the sense that any algorithm to evaluate an arbitrary polynomial must use at least as many operations. Alexander Ostrowski proved in 1954 that the number of additions required is minimal. Victor Pan proved in 1966 that the number of multiplications is minimal. However, when x is a matrix, Horner's method is not optimal.
This assumes that the polynomial is evaluated in monomial form and no preconditioning of the representation is allowed, which makes sense if the polynomial is evaluated only once. However, if preconditioning is allowed and the polynomial is to be evaluated many times, then faster algorithms are possible. They involve a transformation of the representation of the polynomial. In general, a degree-n polynomial can be evaluated using only +2 multiplications and n additions.

Parallel evaluation

A disadvantage of Horner's rule is that all of the operations are sequentially dependent, so it is not possible to take advantage of instruction level parallelism on modern computers. In most applications where the efficiency of polynomial evaluation matters, many low-order polynomials are evaluated simultaneously, so it is not necessary to find parallelism within a single polynomial evaluation.
If, however, one is evaluating a single polynomial of very high order, it may be useful to break it up as follows:
More generally, the summation can be broken into k parts:
where the inner summations may be evaluated using separate parallel instances of Horner's method. This requires slightly more operations than the basic Horner's method, but allows k-way SIMD execution of most of them.

Application to floating-point multiplication and division

Horner's method is a fast, code-efficient method for multiplication and division of binary numbers on a microcontroller with no hardware multiplier. One of the binary numbers to be multiplied is represented as a trivial polynomial, where , and. Then, x is repeatedly factored out. In this binary numeral system,, so powers of 2 are repeatedly factored out.

Example

For example, to find the product of two numbers and m:

Method

To find the product of two binary numbers d and m:

Derivation

In general, for a binary number with bit values the product is
At this stage in the algorithm, it is required that terms with zero-valued coefficients are dropped, so that only binary coefficients equal to one are counted, thus the problem of multiplication or division by zero is not an issue, despite this implication in the factored equation:
The denominators all equal one, so this reduces to
or equivalently
In binary math, multiplication by a power of 2 is merely a register shift operation. Thus, multiplying by 2 is calculated in base-2 by an arithmetic shift. The factor is a right arithmetic shift, a results in no operation, and a results in a left arithmetic shift.
The multiplication product can now be quickly calculated using only arithmetic shift operations, addition and subtraction.
The method is particularly fast on processors supporting a single-instruction shift-and-addition-accumulate. Compared to a C floating-point library, Horner's method sacrifices some accuracy, however it is nominally 13 times faster and uses only 20% of the code space.

Another Application

Horner's method can be used to convert between different positional numeral systems – in which case x is the base of the number system, and the ai coefficients are the digits of the base-x representation of a given number – and can also be used if x is a matrix, in which case the gain in computational efficiency is even greater. In fact, when x is a matrix, further acceleration is possible which exploits the structure of matrix multiplication, and only instead of n multiplies are needed using the 1973 method of Paterson and Stockmeyer.

Polynomial root finding

Using the long division algorithm in combination with Newton's method, it is possible to approximate the real roots of a polynomial. The algorithm works as follows. Given a polynomial of degree with zeros make some initial guess such that. Now iterate the following two steps:
  1. Using Newton's method, find the largest zero of using the guess.
  2. Using Horner's method, divide out to obtain. Return to step 1 but use the polynomial and the initial guess.
These two steps are repeated until all real zeros are found for the polynomial. If the approximated zeros are not precise enough, the obtained values can be used as initial guesses for Newton's method but using the full polynomial rather than the reduced polynomials.

Example

Consider the polynomial
which can be expanded to
From the above we know that the largest root of this polynomial is 7 so we are able to make an initial guess of 8. Using Newton's method the first zero of 7 is found as shown in black in the figure to the right. Next is divided by to obtain
which is drawn in red in the figure to the right. Newton's method is used to find the largest zero of this polynomial with an initial guess of 7. The largest zero of this polynomial which corresponds to the second largest zero of the original polynomial is found at 3 and is circled in red. The degree 5 polynomial is now divided by to obtain
which is shown in yellow. The zero for this polynomial is found at 2 again using Newton's method and is circled in yellow. Horner's method is now used to obtain
which is shown in green and found to have a zero at −3. This polynomial is further reduced to
which is shown in blue and yields a zero of −5. The final root of the original polynomial may be found by either using the final zero as an initial guess for Newton's method, or by reducing and solving the linear equation. As can be seen, the expected roots of −8, −5, −3, 2, 3, and 7 were found.

Divided difference of a polynomial

Horner's method can be modified to compute the divided difference Given the polynomial
proceed as follows
At completion, we have
This computation of the divided difference is subject to less
round-off error than evaluating and separately, particularly when
. Substituting
in this method gives, the derivative of.

History

Horner's paper, titled "A new method of solving numerical equations of all orders, by continuous approximation", was read before the Royal Society of London, at its meeting on July 1, 1819, with Davies Gilbert, Vice-President and Treasurer, in the chair; this was the final of the session before the Society adjourned for its Summer recess. When a sequel was read before the Society in 1823, it was again at the final meeting of the session. On both occasions, papers by James Ivory, FRS, were also read. In 1819, it was Horner's paper that got through to publication in the "Philosophical Transactions". later in the year, Ivory's paper falling by the way, despite Ivory being a Fellow; in 1823, when a total of ten papers were read, fortunes as regards publication, were reversed. Gilbert, who had strong connections with the West of England and may have had social contact with Horner, resident as Horner was in Bristol and Bath, published his own of Horner-type methods earlier in 1823.
Horner's paper in Part II of Philosophical Transactions of the Royal Society of London for 1819 was warmly and expansively welcomed by a in the issue of The Monthly Review: or, Literary Journal for April, 1820; in comparison, a technical paper by Charles Babbage is dismissed curtly in this review. However, the reviewer noted that another, similar method had also recently been published by the architect and mathematical expositor, Peter Nicholson. This theme is developed in a further of some of Nicholson's books in the issue of The Monthly Review for December, 1820, which in turn ends with notice of the appearance of a booklet by Theophilus Holdred, from whom Nicholson acknowledges he obtained the gist of his approach in the first place, although claiming to have improved upon it. The sequence of reviews is concluded in the issue of The Monthly Review for September, 1821, with the concluding that whereas Holdred was the first person to discover a direct and general practical solution of numerical equations, he had not reduced it to its simplest form by the time of Horner's publication, and saying that had Holdred published forty years earlier when he first discovered his method, his contribution could be more easily recognized. The reviewer is exceptionally well-informed, even having cited Horner's preparatory correspondence with Peter Barlow in 1818, seeking work of Budan. The Bodlean Library, Oxford has the Editor's annotated copy of The Monthly Review from which it is clear that the most active reviewer in mathematics in 1814 and 1815 was none other than Peter Barlow, one of the foremost specialists on approximation theory of the period, suggesting that it was Barlow, who wrote this sequence of reviews. As it also happened, Henry Atkinson, of Newcastle, devised a similar approximation scheme in 1809; he had consulted his fellow Geordie, Charles Hutton, another specialist and a senior colleague of Barlow at the Royal Military Academy, Woolwich, only to be advised that, while his work was publishable, it was unlikely to have much impact. J. R. Young, writing in the mid-1830s, concluded that Holdred's first method replicated Atkinson's while his improved method was only added to Holdred's booklet some months after its first appearance in 1820, when Horner's paper was already in circulation.
The feature of Horner's writing that most distinguishes it from his English contemporaries is the way he draws on the Continental literature, notably the work of Arbogast. The advocacy, as well as the detraction, of Horner's Method has this as an unspoken subtext. Quite how he gained that familiarity has not been determined. Horner is known to have made a close reading of John Bonneycastle's book on algebra. Bonneycastle recognizes that Arbogast has the general, combinatorial expression for the reversion of series, a project going back at least to Newton. But Bonneycastle's main purpose in mentioning Arbogast is not to praise him, but to observe that Arbogast's notation is incompatible with the approach he adopts. The gap in Horner's reading was the work of Paolo Ruffini, except that, as far as awareness of Ruffini goes, citations of Ruffini's work by authors, including medical authors, in Philosophical Transactions speak volumes, as there are none — Ruffini's name only appears in 1814, recording a work he donated to the Royal Society. Ruffini might have done better if his work had appeared in French, as had Malfatti's Problem in the reformulation of Joseph Diez Gergonne, or had he written in French, as had :it:Antonio Cagnoli|Antonio Cagnoli, a source quoted by Bonneycastle on series reversion.
Fuller showed that the method in Horner's 1819 paper differs from what afterwards became known as "Horner's method" and that in consequence the priority for this method should go to Holdred. This view may be compared with the remarks concerning the works of Horner and Holdred in the previous paragraph. Fuller also takes aim at Augustus De Morgan. Precocious though Augustus de Morgan was, he was not the reviewer for The Monthly Review, while several others — Thomas Stephens Davies, J. R. Young, Stephen Fenwick, T. T. Wilkinson — wrote Horner firmly into their records, not least Horner, as he published extensively up until the year of his death in 1837. His paper in 1819 was one that would have been difficult to miss. In contrast, the only other mathematical sighting of Holdred is a single named contribution to The Gentleman's Mathematical Companion, an answer to a problem.
It is questionable to what extent it was De Morgan's advocacy of Horner's priority in discovery that led to "Horner's method" being so called in textbooks, but it is true that those suggesting this tend to know of Horner largely through intermediaries, of whom De Morgan made himself a prime example. However, this method qua method was known long before Horner. In reverse chronological order, Horner's method was already known to:
However, this observation on its own masks significant differences in conception and also, as noted with Ruffini's work, issues of accessibility.
Qin Jiushao, in his Shu Shu Jiu Zhang, presents a portfolio of methods of Horner-type for solving polynomial equations, which was based on earlier works of the 11th century Song dynasty mathematician Jia Xian; for example, one method is specifically suited to bi-quintics, of which Qin gives an instance, in keeping with the then Chinese custom of case studies. The first person writing in English to note the connection with Horner's method was Alexander Wylie, writing in The North China Herald in 1852; perhaps conflating and misconstruing different Chinese phrases, Wylie calls the method Harmoniously Alternating Evolution, working the case of one of Qin's quartics and giving, for comparison, the working with Horner's method. Yoshio Mikami in Development of Mathematics in China and Japan published in Leipzig in 1913, gave a detailed description of Qin's method, using the quartic illustrated to the above right in a worked example; he wrote:
However, as Mikami is also aware, it was not altogether impossible that a related work, Si Yuan Yu Jian by Zhu Shijie might make the shorter journey across to Japan, but seemingly it never did, although another work of Zhu, Suan Xue Qi Meng, had a seminal influence on the development of traditional mathematics in the Edo period, starting in the mid-1600s. Ulrich Libbrecht gave a detailed description in his doctoral thesis of Qin's method, he concluded: It is obvious that this procedure is a Chinese invention ... the method was not known in India. He said, Fibonacci probably learned of it from Arabs, who perhaps borrowed from the Chinese. Here, the problems is that there is no more evidence for this speculation than there is of the method being known in India. Of course, the extraction of square and cube roots along similar lines is already discussed by Liu Hui in connection with Problems IV.16 and 22 in Jiu Zhang Suan Shu'', while Wang Xiaotong in the 7th century supposes his readers can solve cubics by an approximation method described in his book Jigu Suanjing.