Polynomial Evaluation

The accurate and efficient computation of univariate polynomials, expressions of the form c ₀ + c ₁ x + c ₂ x ² + + c _n x ⁿ, is important in many core algorithms. This is because polynomials are the normal way of approximating other mathematical functions. For example, one can calculate sin( x) using some truncated version of the standard Taylor series:

Depending on how large x is and the accuracy required in the answer, a moderate number of terms may suffice. Many standard libraries for mathematical functions, including those supplied by Intel and described in Chapter 10 (see also [25][26]), have at their core some such polynomial approximations. Rather than standard Taylor series they often use slightly different minmax polynomials designed to reduce the maximum error in approximation over a chosen interval. The coefficients of such polynomials can be obtained numerically using an algorithm due to Remez [27], and are not in general simple analytical expressions such as . However, these coefficients are created during algorithm design and stored in memory, so the particular c _i usually make no essential difference to the task of making the runtime computation of c ₀ + c ₁ x + c ₂ x ² + + c _n x ⁿ work efficiently and with acceptable rounding error.