Content deleted Content added
Commenting on submission |
→Algorithm: cn tags |
||
Line 21:
=== Preliminaries ===
Consider an arbitrary polynomial <math>p \in \mathbb{R}[x]</math> of [[Degree of a polynomial|degree]] <math>n</math>. Assume that <math>n \geq 3</math>. Define <math>m</math> such that: if <math>n</math> is odd then <math>n = 2m+1</math>, and if <math>n</math> is even then <math>n = 2m+2</math>.{{cn|date=July 2025}}
Unless otherwise stated, all variables represent either [[Real number|real numbers]] or univariate [[Polynomial|polynomials]] with real coefficients. All operations are done over <math>\mathbb{R}</math>.{{cn|date=July 2025}}
Again, the goal is to create an algorithm that returns <math>p(x)</math> given any <math>x</math>. The algorithm is allowed to depend on the polynomial <math>p</math> itself.{{cn|date=July 2025}}
=== Overview ===
Line 37:
where <math>x^2 - \alpha</math> is the divisor. Picking a value for <math>\alpha</math> fixes both the quotient <math>q</math> and the coefficients in the remainder <math>\beta</math> and <math>\gamma</math>. The key idea is to cleverly choose <math>\alpha</math> such that <math>\beta = 0</math>, so that
<math display="block"> p(x) = q(x) \cdot (x^2 - \alpha) + \gamma. </math>{{cn|date=July 2025}}
This way, no operations are needed to compute the remainder polynomial, since it's just a constant. We apply this procedure [[Recursion (computer science)|recursively]] to <math>q</math>, expressing
Line 53:
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 at least <math>n-1</math> roots of <math>p</math> 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 most 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>.{{cn|date=July 2025}}
=== Preprocessing step ===
Line 59:
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.{{cn|date=July 2025}}
<div style="margin-left: 35px;">
Line 83:
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 find such a <math>t</math>.{{cn|date=July 2025}} For example:
<div style="margin-left: 35px;">
Line 96:
=== 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"/><ref name="muller2016"/> It consumes the output of the [[#Preprocessing step|preprocessing step]].{{cn|date=July 2025}}
<div style="margin-left: 35px;">
| |||