多項式評價的準確性，乘法與除法

Question

讓我們說我有X多項式，通過x的功率分爲：

p = (a + x(b + x(c + ..)))/(x**n) 

效率不談，這將是更準確的計算數值，上述或使用部門：

p = (((a/x + b)/x + c)/x + ...) 

感謝

Answer 1

我認爲差異很小，除非有機會x**n溢出或下溢，在這種情況下，您應該使用第二個表達式。

兩個表達式相差在兩個地方：

1. 評價順序相反（...，C，B，a）用於在第一表達和（A，B，C，...）爲第二個表達式。哪一個最好取決於係數的值。
2. 第一個表達式的末尾有.../x**n。正如喬納森解釋的那樣，出於這個原因，可能會期望第二個表達式更準確，因爲它的操作更少。但是，我認爲.../x**n只會導致精度損失最小（與其他您失去準確性的地方相比），除非x**n溢出或下溢。

Answer 2

從理論上講，不應該有任何區別 - 如果值與「無限」的精度精確計算。

Kernighan和Plauger狀態在他們的古董，但優秀的書「Elements of Programming Style」，即：

聰明的程序員曾經說過，「浮點數是像顆顆小堆;每次移動一次，你失去一點沙子，並獲得一點污垢「。

該部門的整體作業略少，這意味着失去沙子和污垢的機會稍微減少。

詳細的分析可能需要查看係數（a，b，c等）以及x的值 - 當x很大時，x很接近零時可能無法正常工作，反之亦然。

Answer 3

提供的答案不正確。

第二個方程p =（（（（a/x + b）/ x + c）/ x + ...）對於精確度只有邊際更差，對速度來說差得多。

爲什麼？乘法的相對誤差只有主要線性項 和一個小的二次項。司在相反引入較高，但 非常小的術語（立方體，四次）：

E =相對誤差，對於這兩個術語

A * B =（1 + E）B（假定爲常數1+ e）= a b（1 + 2e + e^2）//乘法

a/b = a（1 + e）/ b（1 + e）= a/b（1 + e） + E + E^2 + E^3 + ...幾何系列）//除法

所以除法總是比乘法差一點。 出於速度考慮：分區總是慢於乘法， 正常因子可以從3x - 10x變化。因此，如果不通過pow（）計算最後一個因子 ，而是通過嵌套乘法計算，則嵌套的分割比嵌套的乘法要慢 。

x^n可以很容易地通過循環乘以結果來計算 double power = x;對於（n-1） 功率* = x;

如果您使用pow（），請注意它主要是通過 指數和對數計算得來，所需時間遠遠超過必要（100x）。

您是否知道雖然雙精度結果和精確結果之間的誤差仍然很小，但多項式結果爲非常有效對於更高n值的x變化很敏感？ 所以，如果你使用更高的n值得注意，你的答案可能完全脫離標記 ，因爲x中的小錯誤被天文放大。