Knuth Algorithm for Polynomial Evaluation

March 9, 2024

When describing the Modified Stereographic Conformal projection, Snyder refers to “Knuth Algorithm” for efficient evaluation of polynomials. The page number, given in references, probably refers to an earlier edition of TAOCP¹ than the one I have. Took a bit of searching to locate the algorithm; it is in section 4.6.4 (page 487 in 3rd edition) and here is the paragraph describing it:

An alternative procedure for evaluating $u(x + iy)$ is to let $$ \begin{align} &a_1 = u_n, & & b_1 = u_{n−1}, & & r = x + x, & & s = x^2 + y^2; \cr &a_j = b_{j−1} + ra_{j−1}, & & b_j = u_{n−j} − sa_{j−1},& & 1 < j ≤ n. & & \cr \end{align} $$ Then it is easy to prove by induction that $u(z) = za_n +b_n$.

In the above formulas, the polynomial to be evaluated is: $$ u(z) = u_nz^n+u_{n-1}z^{n-1}+\dots +u_1z+u_0 $$

Comparing complexity of this algorithm with classical Horner scheme, we have

In particular for a degree 6 polynomial, as it is used in this application,

The “Kunth Algorithm” saves 3 additions and 8 multiplications. Considering that each inverse computation needs 2 or 3 iterations, that adds up to less than 50 floating-point operations.

These days, when an average CPU has >60 GFLOPS, this difference might be noticeable only for applications converting millions of points.