What are the most accurate algorithms for evaluating a polynomial using floating point arithmetic? The internet seems to suggest that Horner's method is commonly used. In particular I have a cubic polynomial of the form f(x) = a x^3 + b x^2 + c x + d, which I am evaluating in the naive way with floating point arithmetic, and was curious whether some recursive approach or some refactoring would give a more accurate result. That is, a result closer to what I would get if I were to evaluate the polynomial exactly or with a metric ton of precision in Mathematica.
Accurate Polynomial Evaluation in Floating Point
floating point;polynomials
Horner is indeed the most stable way to evaluate a polynomial (and you get the bonus of evaluating its derivatives with not too much extra cost). Higham presents a nice error analysis of the algorithm (Accuracy and stability of numerical algorithms, 2nd edition, p.94). He also presents an algorithm that includes a running error bound so you have an idea on the difference between the real value and what Horner calculated (Algorithm 5.1 on p.95).If your case is limited to cubic polynomials and you're worried about loop overhead, you could unroll the loops by hand. But I doubt you will gain much. Stick to the tried and tested.  