Content deleted Content added
Add link to Eve |
Add more citations |
||
Line 41:
<math display="block"> p(x) = \left( \left( q(x) \cdot (x^2 - \alpha_m) + \gamma_m \right) \cdots \right) \cdot (x^2 - \alpha_1) + \gamma_1. </math>
After <math>m</math> recursive calls, the quotient <math>q</math> is either a [[Linear function (calculus)|linear]] or a [[Quadratic function|quadratic]] polynomial. In this base case, the polynomial can be evaluated with (say) [[Horner's method]].<ref name="knuth1962"/><ref name="overill1997"/>
==== "Preconditioning" ====
Line 55:
=== Preprocessing step ===
The following algorithm is run once for a given polynomial <math>p</math>.<ref name="knuth1962"/><ref name="overill1997"/> Its results are used by the [[#Evaluation step|evaluation step]], and they can be reused across many calls to that step.
At this point, the values of <math>x</math> that <math>p</math> will be evaluated on are not known.
Line 94:
=== Evaluation step ===
The following algorithm evaluates <math>p</math> at some, now known, point <math>x</math>.<ref name="knuth1962"/><ref name="eve1964"/><ref name="overill1997"/> It consumes the output of the [[#Preprocessing step|preprocessing step]].
<div style="margin-left: 35px;">
Line 112:
<math display="block">y \gets y \cdot (s - \alpha_i),</math>
saving an addition.<ref name="eve1964"/>
== Analysis ==
In total, evaluation using the Knuth–Eve algorithm for a polynomial of degree <math>n</math> requires <math>n</math> additions and <math>\lfloor n/2 \rfloor + 2</math> multiplications, assuming <math>t</math> is chosen optimally.<ref name="eve1964"/>
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"/>{{Better source needed}}
| |||