floating-point - 评估多项式-浮点还是优化问题？

Question

从数字食谱:

We assume that you know enough never to evaluate a polynomial this way: p=c[0]+c[1]*x+c[2]*x*x+c[3]*x*x*x+c[4]*x*x*x*x; ...

显然我不够了解...

这仅仅是一个优化问题还是一个浮点算术问题，为什么？

Answer 1

您可以将p=c[0]+c[1]*x+c[2]*x*x+c[3]*x*x*x+c[4]*x*x*x*x;计算为:

p=c[0]+(c[1]+(c[2]+(c[3]+c[4]*x)*x)*x)*x;

第二种形式的乘法要少得多。第二种形式称为“霍纳氏”。

Is this only an optimization issue or is it also a floating point arithmetic issue and why?

这主要是一个优化问题。但是，某些现代处理器具有浮点运算，可以在单个指令中执行乘法和加法运算，而无需中间四舍五入，而且大多数程序员看到的好处仍然是优化，这也意味着结果更准确。

Horner的形式非常适合使用 fused-multiply-add instruction进行计算。

最后，为了完整起见，我应该指出，如果多项式以更并行的形式呈现给它们，现代处理器将更加高效。有关扎实的解释，请参见 Estrin's scheme或 this blog post。您的书并不暗示了解Estrin方案的要求。它只是在暗示了解霍纳方案的要求。