计算多项式的最有效方法

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;
}

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

但是我想知道是否有更好的方法来计算这个多项式？

** 对于任何认为这是不同计算的人：我确实测试了上面的函数。它对 y += array_a[index] * Math.Pow(x, index); 做同样的事情，他们计算出相同的结果。

谢谢。

Answer 1

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

… Horner's method requires only n additions and n multiplications, and its storage requirements are only n times the number of bits of x. …

Horner's method is optimal, in the sense that any algorithm to evaluate an arbitrary polynomial must use at least as many operations. Alexander Ostrowski proved in 1954 that the number of additions required is minimal. Victor Pan proved in 1966 that the number of multiplications is minimal.

如果你需要计算多项式的次数非常多，而且次数很高，那么有一些方法可以将多项式的表示形式进行变换（预处理），使得数乘法减少到 ⌊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/compiler 可能能够为您完成此转换，甚至可以使用 SIMD 自动使其非常快速。无论如何，对于这种微优化，在提交最终解决方案之前始终进行概要分析。

计算多项式的最有效方法

Most efficient way to compute a polynomial

java

polynomial-math