Content deleted Content added
Better choice of `t`. |
Algorithm for choosing `t` |
||
Line 70:
==== 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 also 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"/>
It is always possible to choose <math>t</math> in this way. For example:
<div style="margin-left: 35px;">
{{framebox|blue}}
* If <math>r_1 \in \mathbb{R}</math>:
** If <math>r_2 \in \mathbb{R}</math>: <math display="inline">t = \tfrac{1}{2} (r_1 + r_2)</math>
** Else: <math>t = \text{Re}(r_2)</math>
* Else: <math>t = \text{Re}(r_1)</math>
{{frame-footer}}
</div>
=== Evaluation step ===
Line 87 ⟶ 98:
{{frame-footer}}
</div>
Assuming <math>t</math> is chosen optimally, <math>\gamma_1 = 0</math>. So, the final iteration of the loop can instead run
<math display="block">y \gets y \cdot (s - \alpha_i).</math>
== Analysis ==
| |||