计算多项式的最有效方法

Question

多项式：a0x^0 + a1x^1 +a2x^2 + a3x^3 + ... + anx^n

数组：array_a[] = {a0, a1, a2, a3 ... an};

我用Java写了一个计算多项式的函数：

public double cal(double x) {
    double y = 0.0;
    for (int index = array_a.length - 1; index >= 0; index--) {
        y = array_a[index] + y * x;
    }
    return y;
}

这种方法似乎比循环 y += array_a[index] * Math.Pow(x, index); 快5倍。

但是我在想是否有更好的计算多项式的方法？

对于那些认为这是不同计算的人：我测试过上述函数。它与 y += array_a[index] * Math.Pow(x, index); 做的是相同的事情，它们会计算出相同的结果。

谢谢。

- Louis Tran

---

他使用多项式等于a0 + x * (a1 + x*(a2 +... ))。 - J Fabian Meier

有更好的方法吗？似乎已经是最好的方法了。尽可能少的计算。你为什么问呢？你不喜欢哪一部分？ - Andreas

@Andreas 是的，我也这么认为。这是最好的方法，但我的教授仍然要求她的学生优化它。所以我正在尝试找到更好的方法。 - Louis Tran

也许他想要这个double y = 0; double x_n = 1; for (i = 0; i < length; i++) { y += array[i] * x_n; x_n *= x; } - 从性能上来看，它可能与你的版本相当。 - assylias

无论如何调试，您都必须执行 n 次加法操作和 n+1 次乘法操作。这是无法减少的。通过使用 a0 + x * (a1 + x*(a2 +... )) 公式，您已成功消除了幂运算。好吧，技术上说，通过乘以 x^0 可以消除，因此只需要 n 次乘法操作。您的代码当前正在执行 n+1 次加法和乘法操作，因此可以稍微调整一下。请注意，n = array_a.length - 1. - Andreas

Answer 1

这是Horner方法。如果你只想每个多项式计算一次，这是最有效的算法：

"… Horner方法只需要n次加法和n次乘法，并且其存储要求仅为x位数的n倍。… "

Horner方法是最优的，因为任何算法都必须使用至少与Horner方法相同数量的操作来评估任意多项式。 Alexander Ostrowski在1954年证明了所需的添加数量最小。 Victor Pan在1966年证明了所需的乘法数量最小。

如果您需要极其频繁地计算多项式，而且阶数非常高，则有方法可以转换多项式的表示（预处理），以便将乘法次数减少到⌊n/2⌋+2。虽然如此，但这似乎不太实用，至少我从未在实践中看到过。我找到了一篇在线论文，如果您感兴趣，可以了解一些算法。

此外，在论文中提到，由于CPU体系结构的原因，如果分别计算偶数和奇数项，它可能更有效，因此它们可以放置在并行管道中：

public double cal(double x) {
    double x2 = x * x;
    double y_odd = 0.0, y_even = 0.0;
    int index = array_a.length - 1;
    if (index % 2 == 0) {
        y_even = array_a[index];
        index -= 1;
    }
    for (; index >= 0; index -= 2) {
        y_odd = array_a[index] + y_odd * x2;
        y_even = array_a[index-1] + y_even * x2;
    }
    return y_even + y_odd * x;
}

- kennytm