Horner's method

The algorithm is based on Horner's rule, in which a polynomial is written in nested form:

This is optimal, since there are polynomials of degree n that cannot be evaluated with fewer arithmetic operations.

It is a variant of the Newton–Raphson method made more efficient for hand calculation by application of Horner's rule.

are constant coefficients, the problem is to evaluate the polynomial at a specific value

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;

If numerical data are represented in terms of digits (or bits), then the naive algorithm also entails storing approximately

[3] Horner's method is optimal, in the sense that any algorithm to evaluate an arbitrary polynomial must use at least as many operations.

However, if preconditioning is allowed and the polynomial is to be evaluated many times, then faster algorithms are possible.

[6] 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.

This requires slightly more operations than the basic Horner's method, but allows k-way SIMD execution of most of them.

Modern compilers generally evaluate polynomials this way when advantageous, although for floating-point calculations this requires enabling (unsafe) reassociative math[citation needed].

One of the binary numbers to be multiplied is represented as a trivial polynomial, where (using the above notation)

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:

In binary (base-2) math, multiplication by a power of 2 is merely a register shift operation.

The multiplication product can now be quickly calculated using only arithmetic shift operations, addition and subtraction.

Compared to a C floating-point library, Horner's method sacrifices some accuracy, however it is nominally 13 times faster (16 times faster when the "canonical signed digit" (CSD) form is used) and uses only 20% of the code space.

[7] 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.

[8] Using the long division algorithm in combination with Newton's method, it is possible to approximate the real roots of a polynomial.

Using Newton's method the first zero of 7 is found as shown in black 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 zero for this polynomial is found at 2 again using Newton's method and is circled in yellow.

This computation of the divided difference is subject to less round-off error than evaluating

Horner's paper, titled "A new method of solving numerical equations of all orders, by continuous approximation",[12] was read before the Royal Society of London, at its meeting on July 1, 1819, with a sequel in 1823.

[12] Horner's paper in Part II of Philosophical Transactions of the Royal Society of London for 1819 was warmly and expansively welcomed by a reviewer[permanent dead link‍] 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.

Unlike his English contemporaries, Horner drew on the Continental literature, notably the work of Arbogast.

Horner is also known to have made a close reading of John Bonneycastle's book on algebra, though he neglected the work of Paolo Ruffini.

In reverse chronological order, Horner's method was already known to: Qin Jiushao, in his Shu Shu Jiu Zhang (Mathematical Treatise in Nine Sections; 1247), 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.

Yoshio Mikami in Development of Mathematics in China and Japan (Leipzig 1913) wrote:"... who can deny the fact of Horner's illustrious process being used in China at least nearly six long centuries earlier than in Europe ... We of course don't intend in any way to ascribe Horner's invention to a Chinese origin, but the lapse of time sufficiently makes it not altogether impossible that the Europeans could have known of the Chinese method in a direct or indirect way.

"[20]Ulrich Libbrecht concluded: It is obvious that this procedure is a Chinese invention ... the method was not known in India.

[21] 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.