<p><a href="https://en.wikipedia.org/wiki/Estrin%27s_scheme" rel="nofollow noreferrer">Estrin's Method</a> is an alternative to <a href="https://en.wikipedia.org/wiki/Horner%27s_method" rel="nofollow noreferrer">Horner's method</a> for evaluating polynomials. To evaluate a polynomial <span class="math-container">$P(x)=\sum_{i=0}^7 a_i x^i$</span> at a point <span class="math-container">$x\in\mathbb R$</span>, it first computes the powers <span class="math-container">$x^2$</span> and <span class="math-container">$x^4$</span> and then uses the decomposition:</p>
<p><span class="math-container">$$P(x) = (a_0 + a_1 x) + (a_2 + a_3x) x^2 + ((a_4 + a_5 x) + (a_6 + a_7 x) x^2)x^4.$$</span></p>
<p>This turns out to be faster than Horner's method on modern computers, since the four <span class="math-container">$a_i + a_{i+1}x$</span> terms can be computed in parallel.</p>
<p>Books like &quot;Accuracy and Stability of Numerical Algorithms, Second Edition&quot; study the numerical accuracy of Horner's method.
See also <a href="https://scicomp.stackexchange.com/questions/13023">this discussion</a> on the other Computer Science stackexchange, or <a href="https://math.stackexchange.com/questions/1436643/horners-method">this question</a> on math stackexchange.</p>
<p>However, I've been unable to find any papers covering Estrin's method.
Is anyone aware whether Estrin's method is as stable as Horner's method? Or how much worse?</p>

CC BY-SA 4.0
2023-01-31T06:40:25.717Z
If anything, I’d expect it to be better rather than worse. But I’m no expert in these matters.
Emil Jeřábek
CC BY-SA 4.0
2023-01-31T07:31:47.850Z
From experiments here it sadly seems worse: https://github.com/boostorg/math/pull/932 I'd be interested in ideas for making it more accurate.
Thomas Ahle
<reference-request><polynomials><na.numerical-analysis>
Error analysis of Estrin's method
Thomas Ahle
# Error analysis of Estrin's method

(Asked by: username_0 on 2023-01-31)

[Estrin's Method](https://en.wikipedia.org/wiki/Estrin%27s_scheme) is an alternative to [Horner's method](https://en.wikipedia.org/wiki/Horner%27s_method) for evaluating polynomials. To evaluate a polynomial $P(x)=\sum\_{i=0}^7 a\_i x^i$ at a point $x\in\mathbb R$, it first computes the powers $x^2$ and $x^4$ and then uses the decomposition:

$$P(x) = (a\_0 + a\_1 x) + (a\_2 + a\_3x) x^2 + ((a\_4 + a\_5 x) + (a\_6 + a\_7 x) x^2)x^4.$$

This turns out to be faster than Horner's method on modern computers, since the four $a\_i + a\_{i+1}x$ terms can be computed in parallel.

Books like "Accuracy and Stability of Numerical Algorithms, Second Edition" study the numerical accuracy of Horner's method.
See also [this discussion](https://scicomp.stackexchange.com/questions/13023) on the other Computer Science stackexchange, or [this question](https://math.stackexchange.com/questions/1436643/horners-method) on math stackexchange.

However, I've been unable to find any papers covering Estrin's method.
Is anyone aware whether Estrin's method is as stable as Horner's method? Or how much worse?

**Tags:** reference-request, polynomials, na.numerical-analysis
> **Comments:**
> **username_1**: If anything, I’d expect it to be better rather than worse. But I’m no expert in these matters.  
> **username_0**: From experiments here it sadly seems worse: https://github.com/boostorg/math/pull/932 I'd be interested in ideas for making it more accurate.  

---

## 0 answers

