评估多项式 - 浮点或优化问题？

Question

从数字食谱:

我们假设您知道永远不会以这种方式评估多项式: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;

第二种形式的乘法少得多.第二种形式叫做"Horner's".

这只是一个优化问题,还是浮点运算问题,为什么？

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

Horner的形式非常适合使用这种融合乘法加法指令进行计算.

最后,为了完整起见,我应该指出,如果多项式以更多并行性的形式呈现给它们,那么现代处理器可以更高效.例如,参见Estrin的方案或此博客文章,了解实际的解释.你的书并没有提到了解Estrin计划的要求.它只是提到了解霍纳计划的要求.