计算多项式的最有效方法

Question

多项式: a0x^0 + a1x^1 +a2x^2 + a3x^3 +…+ anx^n

数组: array_a[] = {a0，a1，a2，a3 .A}；

我用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);做同样的事情，它们计算相同的结果。

谢谢。

Answer 1

这是Horner的方法。如果您只想每一个多项式计算一次，this is the most efficient algorithm

…霍纳方法只需n个加法和n个乘法，其存储要求仅为x.…位数的n倍。 Horner的方法是最优的，因为任何计算任意多项式的算法都必须至少使用同样多的运算。在1954年证明了所需增加的数量是极小的。维克多·潘在1966年证明了乘法的次数是最少的。

如果你需要对多项式进行极多次的计算，而且计算的程度很高，那么就有一些方法可以将多项式的表示法(预处理)减少到⌊n/ 2⌋+2。但这似乎不太实际，至少我在野外从未见过。I've found an online paper that describes some of the algorithms if you are interested。

本文还提到，由于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;
}

JIT/编译器可能能够为您完成此转换，甚至可以使用SIMD自动地使其非常快。无论如何，对于这种微观优化，总是在提交最终解决方案之前的概要文件。