Knuth–Eve algorithm: Difference between revisions

Revision as of 06:06, 26 July 2025

Revision as of 06:08, 26 July 2025

Line 42:

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 all the 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 all 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 Steps ===