我记得在某处读过（也许有人可以帮助记住在哪里），有一种方法可以最快地评估多项式。有些东西让我想起它与 Vietta 的公式有关，或者说 0 幂系数是多项式的任何因子的 0 幂系数的乘积。
我知道维基百科说这是霍纳评估最快的方案。但我记得您实际上根本不必以这种方式进行评估-它与根源有关吗？
我所知道的是，有一种评估多项式的方法，当你看到它时，它会给你一种“哦，这很聪明”的感觉，但这并不太难，而且很明显。
任何善良或聪明的人可以帮助我吗？
它类似于“您可以通过...在 x 处评估 P”，然后有一个非常简单的小东西实际上避免了必须按照多项式次数的顺序进行任何真正的加法和乘法运算。
我认为您正在寻找快速傅立叶变换，在 FFT 上查看此 PowerPoint也很好。事实上，当您想要计算 n 个不同点的多项式值时，FFT 很有用，即 O(n log n) 并且比霍纳算法快得多。
FFT 使用单位的 n 次方根的幂，并使用它们之间的关系，因此当您想要计算 n 个不同的点值时非常快。
您是否不止一次评估多项式？多项式特别简单吗？考虑以下多项式：
f(a) = a^(14)
如果我们想减少评估所需的乘法次数，我们可以从加法链求幂f(a)计算最小加法链：
((a × a→b) × b→d) × d × d × b
这表明我们可以f(a)仅使用 5 次乘法来计算。对于具有小系数的固定多项式，这可以显着节省。维基百科注释：
在实践中......最短加法链求幂主要用于小的固定指数，其中最短链可以预先计算并且不会太大。
对于许多f(a)可以改变另一种方法的实际情况可能是合适的，但值得注意的是替代解决方案！