Estrin's scheme evaluates a polynomial by grouping adjacent coefficients into pairs and combining the
resulting expressions in a binary tree. For 
, the first stage rewrites the
polynomial as
 |
where 
uses the floor function and 
when 
is even. The expressions 
can be evaluated in parallel. The scheme then
pairs the new coefficients in the same way, using
in place of 
and squaring the evaluation point at each stage until a single
value remains (Estrin 1960, pp. 35-36).
For a cubic polynomial 
, this gives
 |
The evaluation tree has logarithmic depth in the number of coefficients. By comparison, Horner's rule evaluates the polynomial through a linear chain of dependent operations.
The compensated variant of Yu et al. (2026) uses error-free transformations to recover local roundoff errors and compute a
correction using binary64 floating-point
arithmetic. With rounding to nearest in the normal range, for 
and fixed polynomial
degree at least two, their relative error bound
has the form 
, where 
is the unit roundoff and 
measures the sensitivity of 
to componentwise relative perturbations of its coefficients
(Yu et al. 2026, p. 426).
