Knuth–Eve algorithm: Difference between revisions

Revision as of 05:53, 27 July 2025

Revision as of 06:15, 27 July 2025

Line 53:

{{framebox|blue}}

* Let <math>r_1, \cdots, r_n \in \mathbb{C}</math> be the complex roots of <math>p</math>, sorted in descending order by real part

* Choose any <math display="inline">t \geq \text{Re}(r_2)</math>

* Set <math>p \gets p(x + t)</math>

<hr/>

Line 67:

{{frame-footer}}

</div>

==== Better choice of <math>t</math> ====

While any <math>t \geq \text{Re}(r_2)</math> can work, it is possible to remove one addition during evaluation if <math>t</math> is chosen such that two roots of <math>p(x + t)</math> are symmetric about the origin. In that case, <math>\alpha_1</math> can be chosen such that the shifted polynomial has a factor of <math>x^2 - \alpha_1</math>, so <math>\gamma_1 = 0</math>.<ref name="eve1964"/>

=== Evaluation step ===

Line 86 ⟶ 90:

== Analysis ==

In total, evaluation using the Knuth-Eve algorithm for a polynomial of degree <math>n</math> requires <math>n+1</math> additions and <math>\lfloor n/2 \rfloor + 2</math> multiplications, assuming <math>t</math> is chosen optimally.

No algorithm to evaluate a given polynomial of degree <math>n</math> can use fewer than <math>n</math> additions or fewer than <math>\lceil n/2 \rceil</math> multiplications during evaluation. This result assumes only addition and multiplication are allowed during both preprocessing and evaluation.<ref name="erickson2003"/>

The Knuth-Eve algorithm is not [[Condition number|well-conditioned]], and it can be significantly affected by [[round-off error]].<ref name="mesztenyi1967"/>

== Notes ==