Editing Horner's method (section)

====Parallel evaluation====
{{see also|Estrin's scheme}}
A disadvantage of Horner's rule is that all of the operations are [[data dependency|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 (for each pixel or polygon in computer graphics, or for each grid square in a numerical simulation), 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:
<math display="block">\begin{align}
p(x)
& = \sum_{i=0}^n a_i x^i \\[1ex]
& = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots + a_n x^n \\[1ex]
& = \left( a_0 + a_2 x^2 + a_4 x^4 + \cdots\right) + \left(a_1 x + a_3 x^3 + a_5 x^5 + \cdots \right) \\[1ex]
& = \left( a_0 + a_2 x^2 + a_4 x^4 + \cdots\right) + x \left(a_1 + a_3 x^2 + a_5 x^4 + \cdots \right) \\[1ex]
& = \sum_{i=0}^{\lfloor n/2 \rfloor} a_{2i} x^{2i} + x \sum_{i=0}^{\lfloor n/2 \rfloor} a_{2i+1} x^{2i} \\[1ex]
& = p_0(x^2) + x p_1(x^2).
\end{align}</math>

More generally, the summation can be broken into ''k'' parts:
<math display="block">p(x)
= \sum_{i=0}^n a_i x^i
= \sum_{j=0}^{k-1} x^j \sum_{i=0}^{\lfloor n/k \rfloor} a_{ki+j} x^{ki}
= \sum_{j=0}^{k-1} x^j p_j(x^k)</math>
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. Modern compilers generally evaluate polynomials this way when advantageous, although for [[floating-point]] calculations this requires enabling (unsafe) reassociative math{{Citation needed|date=February 2022}}. Another use of breaking a polynomial down this way is to calculate steps of the inner summations in an alternating fashion to take advantage of [[instruction-level parallelism]].