D. Knuth's polynomial representation

Directly to the input form

• In 1969 D. Knuth has shown that every real polynomial p(x) of degree n >= 4 can be evaluated using floor(n/2) + 2 multiplications and n+1 additions.
• For n=5 this are 2 multiplications and 6 additions, clearly less than used by Horners scheme (which however has been proven to be complexity optimal if the MacLaurin representation is used as input).
• In order to achieve Knuth's better complexity the polynomial must be represented in an other form, such that this all makes sense only if subsequently its values are required for a hugh number of arguments. This new representation reads as follows:
  p(x) = (...((q(x+ρ)((x+ρ)²-z₁)+R₁) ((x+ρ)²-z₂)+R₂)...) ((x+ρ)²-z_m)+R_m
• Here n is either 2m or 2m+1, q(.) is either quadratic or linear and z_i resp. R_i are real coeffcients, ρ is used for a shift of the origin.
• Using results from complex analysis one can show that this representation is always possible, provided the polynomial has zeroes with nonnegative real part. This property however is always obtainable using a shift of the origin, using an upper bound for the absolute value of all zeroes, which is readily available. Here we use Marden's bound for this:
  |z| <= ρ=2*max{ |a_n-i/a_n|^1/i : i=1,...,n }
  where the a_i are the coefficients of p in the monomial basis and a_n denotes the coefficient of xⁿ. For this reason there appears the term x+ρ and not x itself in this representation. -ρ is what is called ''base point'' in the output of this program. The numbers z_i are the zeroes of the polynomial build from the odd numbered coefficients of the shifted polynomial and the R_i are the remainders in Euclids polynomial division. (The proof that those z_i are indeed always real uses some deep results from complex analysis)
• In a practical application the computed zeroes and remainders are perturbed by roundoff effects and in addition due to the necessary shift of the origin the computed representation might be the source of increased roundoff sensitivity of p's evaluation. Therefore the usefulness of this must be checked subsequently (for example if one wishes a speed up in the evaluation of a polynomial approximation to a complicated transcendental function).
• We compare the evaluation of the representation in the monomial basis and the new one in the interval [-ρ,ρ]

Input

• The degree n of p. Important: n >= 4.
• The coefficients a_n, ... ,a₀ in the monomial basis. a_n is the coefficient of xⁿ. Important also: a_n*a₀ notequal 0.

Output

• The input coefficients.
• The complete Taylor development at the shifted origin.
• The odd numbered coefficients.
• The zeroes z_i and division remainders R_i. In the polynomial division by a quadratic term of course a linear remainder should occur: there is a test output for the (theoretically zero) coefficient of x
• A table of the differences of the evaluation of p for equidistant real arguments in [-ρ,ρ] for the representation in the monomial basis by Horners scheme and for the new representation.

Questions ?!

• When and why you get sometimes (but not always) large deviations in the evaluation of the polynomial?

To the input form