多项式评估精度，乘法与除法
假设我有 x 的多项式，除以 x 的幂：
p = (a + x(b + x(c + ..)))/(x**n)
除了效率之外，这将是更准确的数值计算，上面或使用除法：
p = (((a/x + b)/x + c)/x + ...)
谢谢
let us say I have have polynomial in x, divided by a power of x:
p = (a + x(b + x(c + ..)))/(x**n)
efficiency aside, which would be more accurate computation numerically, the above or using division:
p = (((a/x + b)/x + c)/x + ...)
thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
理论上，如果以“无限”精度准确计算值，则不应该有任何差异。
Kernighan 和 Plauger 在他们古老但优秀的书“编程风格的元素”中指出，那：
该部门的总体业务量略少，这意味着流失沙子和沾污的机会略少。
详细的分析可能需要查看系数（a、b、c 等）以及 x 的值 - 当 x 很大时有效的方法可能在 x 接近零时无效，反之亦然。
In theory, there shouldn't be any difference - if the values are calculated accurately with 'infinite' precision.
Kernighan and Plauger state in their antique but excellent book 'Elements of Programming Style', that:
The division has slightly fewer operations overall, which means there is slightly less opportunity to lose sand and gain dirt.
A detailed analysis would probably require a look at the coefficients (a, b, c, etc) as well perhaps as the value of x - what works when x is huge may not work well when x is close to zero, nor vice versa.
我认为差异很小，除非
x**n有可能溢出或下溢，在这种情况下您应该使用第二个表达式。这两个表达式有两处不同：
.../x**n。正如乔纳森解释的那样，出于这个原因，第二个表达式可能会更准确，因为它的操作较少。但是，我认为.../x**n只会导致最小的准确性损失（与其他失去准确性的地方相比），除非x**n代码> 上溢或下溢。I think the difference is minimal, unless there is a chance that
x**noverflows or underflows, in which case you should use the second expression.The two expressions differ in two places:
.../x**nat the end. As Jonathan explains, for that reason it may be expected that the second expression is more accurate, because it has fewer operations. However, I think that the.../x**ncauses only a minimal loss of accuracy (compared to other places where you lose accuracy), unless thex**noverflows or underflows.不幸的是，所提供的答案是错误的。
第二个方程 p = (((a/x + b)/x + c)/x + ...) 只是边际更差
对于准确性来说，而对于速度来说，情况就更糟了。
为什么 ？乘法的相对误差只有主线性项
和一个小的二次项。相比之下除法引入更高，但是
非常小的项（三次、四次）：
e = 相对误差，假设两项均为常数
a*b = a(1+e)b(1+e) = ab (1+2e+ e^2) // 乘法
a/b = a(1+e)/b(1+e) = a/b (1+e)(1+e+e^2+e^3+...几何series) // 除法
所以除法总是比乘法差一点。
出于速度考虑：除法总是比乘法慢，
正常系数可能在 3x - 10x 之间变化。所以嵌套划分很多
如果不计算最后一个因子，则比嵌套乘法慢
x^n 不是通过 pow()，而是通过嵌套乘法。
x^n 可以通过循环乘以结果轻松计算
双倍幂=x；
对于 (n-1)
功率*=x；
如果您使用 pow()，请注意它通常可以通过以下方式方便地计算
指数和对数，花费的时间比必要的多得多（100x）。
您是否知道，虽然双精度结果和精确结果之间的误差仍然很小，
对于更高 n 的多项式结果对 x 的变化非常敏感？！
因此，如果您使用更高的 n，请注意您的答案可能完全不正确
因为 x 中的小误差会被放大到天文数字。
The answers provided are unfortunately wrong.
The second equation p = (((a/x + b)/x + c)/x + ...) is only marginal worse
for accuracy and much, much worse for speed.
Why ? The relative errors for multiplication has only the main linear term
and a small quadratic term. Division in contrast introduces higher, but
very small terms (cubic, quartic):
e = relative error, assumed constant for both terms
a*b = a(1+e)b(1+e) = ab (1+2e+e^2) // multiplication
a/b = a(1+e)/b(1+e) = a/b (1+e)(1+e+e^2+e^3+...geometric series) // division
So division is always a bit worse than multiplication.
For speed considerations: Divisions are always slower than multiplications,
the normal factor can vary from 3x - 10x. So nested divisions are much
slower than nested multiplications if you don't compute the last factor
x^n not by pow(), but by nested multiplication.
The x^n can be easily computed by a loop multiplying the result
double power = x;
for (n-1)
power *= x;
If you use pow(), be aware that it is mostly conveniently computed by
exponential and logarithm, taking much more time than necessary (100x).
Are you aware that while the error between double and exact result remains small,
polynominal results are very sensitive to changes of x for higher n's ?!
So if you use higher n's be aware that your answers may be totally off the mark
because small errors in x are astronomically amplified.