Knuth–Eve algorithm: Difference between revisions

Revision as of 06:37, 27 July 2025

Revision as of 06:40, 27 July 2025

Line 44:

<math display="block"> p(x) = p^e(x^2) + x \cdot p^o(x^2). </math>

If every [[Zero of a function#Polynomial roots|root]] of <math>p^o</math> is real, then it is possible to write <math>p</math> in the form given above. Each <math>\alpha_i</math> is a different root of <math>p^o</math>, counting [[Multiplicity (mathematics)#Multiplicity of a root of a polynomial|multiple roots]] as distinct.<ref name="overill1997"/> Furthermore, if allat theleast <math>n-1</math> roots of <math>p</math> (except perhaps one) lie in one half of the [[Complex number|complex plane]], then every root of <math>p^o</math> is real.<ref name="eve1964"/>

Ultimately, it may be necessary to "precondition" <math>p</math> by shifting it {{--}} by setting <math>p(x) \gets p(x + t)</math> for some <math>t</math> {{--}} to endow it with the structure that allmost of its roots lie in one half of the complex plane. At runtime, this shift has to be "undone" by first setting <math>x \gets x - t</math>.

=== Preprocessing step ===