从根部高效计算多项式系数

我有一个单调多项式的根，即

p(x) = (x-x_1)*...*(x-x_n)

我需要系数 a_n, ..., a_0

p(x) = x^n + a_{n-1}x^{n-1} + ... + a_0.

有谁知道一个计算效率高这样做的方法？如果有人知道 C/C++ 实现，这实际上是最好的。 （我已经看过 GSL，但它没有提供功能。）

当然，我知道如何用数学方法来计算它。我知道，系数a_i是子集的所有乘积之和n-i元素。但如果我用愚蠢的方式来做，这意味着迭代所有子集，我需要

sum^{n-1}_{k=1} ( k choose n) * (k-1)

乘法和

sum^n_{k=0} ( k choose n) - n

补充。因此这两项都随着增长O(n!)，转换列表的计算量太大n根入列表n系数。我相信一定有某种智能方法可以重用大部分中间结果，但我没有找到。

你可以在以下位置执行此操作O(n^2)如果您逐步构建多项式，则非常容易。让我们定义一下：

p_k(x) = (x-x_1)*...*(x-x_k)

That is p_k(x)是第一个的乘法k (x-x_i) of p(x)。我们有：

p_1(x) = x-x_1

换句话说，系数数组 (a) 将是（索引从 0 开始，从左边开始）：

-x_1 1

现在假设我们有系数数组p_k(x):

a_0 a_1 a_2 ... a_k

（边注：a_k是 1)。现在我们要计算p_k+1(x)，这是（注意k+1是索引，没有按1)求和：

p_k+1(x) = p_k(x)*(x-x_k+1)
=> p_k+1(x) = x*p_k(x) - x_k+1*p_k(x)

将其转换为系数数组，这意味着新系数是先前的系数向右移动（x*p_k(x)）减去k+1次根乘以相同的系数（x_k+1*p_k(x)):

           0   a_0 a_1 a_2 ... a_k-1 a_k
- x_k+1 * (a_0 a_1 a_2 a_3 ... a_k)
-----------------------------------------
-x_k+1*a_0 (a_0-x_k+1*a_1) (a_1-x_k+1*a_2) (a_2-x_k+1*a_3) ... (a_k-x_k+1*a_k-1) a_k

（旁注：这就是如何a_k留下1）有你的算法。从...开始p_1(x)（甚至p_0(x) = 1）并通过上述公式为多项式的每个根逐步构建系数数组。