Knuth–Eve algorithm: Difference between revisions

Revision as of 06:12, 26 July 2025

Revision as of 06:24, 26 July 2025

Line 12:

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>.

Unless otherwise specifiedstated, all variables represent either real numbers or univariate polynomials with real coefficients. All operations are done over <math>\mathbb{R}</math>.

Again, the goal is to create an algorithm that returns <math>p(x)</math> given any <math>x \in \mathbb{R}</math>. The algorithm is allowed to depend on the polynomial <math>p</math> itself. And ideally, it would use as few operations {{--}} as few additions and multiplications {{--}} as possible.

=== Overview ===

==== Key Ideaidea ====

Using [[polynomial long division]], we can write

Line 44:

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 Stepsstep ===

The following algorithm is run once for a fixed polynomial <math>p</math>. 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.

<div style="margin-left: 35px;">

Line 59 ⟶ 63:

</div>

=== RuntimeEvaluation Stepsstep ===

The following algorithm evaluates <math>p</math> at some now known point <math>x</math>. It consumes the output of the [[#Preprocessing step|preprocessing step]].

== Notes ==