我需要在C++中编写函数，以有效地找到给定有理函数(P(x)/Q(x))的泰勒级数的系数。
函数参数将是多项式的幂(在分母和分母中相等)，两个具有多项式系数和展开项数量的数组。
我的想法是跟随。
考虑身份
P(x) / Q(x) = R(x) + ...
其中
R(x)是一个多项式，其项数等于我需要找到的系数数。然后我可以将双方乘以Q(x)并得到P(x) = R(x) * Q(x)
R(x) * Q(x) - P(x) = 0
因此，所有系数应为零。这是具有O(n ^ 3)算法求解的方程组。 O(n ^ 3)并没有我想要的那么快。
有没有更快的算法？
我知道级数的系数满足线性递归关系。
这使我认为O(n)算法是可行的。
最佳答案
我要描述的算法通过formal power series在数学上是合理的。泰勒级数的每个函数都有一个正式的幂级数。反之则不成立，但是如果我们对具有泰勒级数的函数进行算术运算并得到具有泰勒级数的函数，那么我们就可以对形式幂级数进行相同的算术运算并得到相同的答案。
形式幂级数的长除法算法就像您在学校可能学过的long division算法一样。我将在示例(1 + 2 x)/(1 - x - x^2)上进行演示，该示例的系数等于Lucas numbers。
分母必须具有非零常数项。我们首先编写分子，这是第一个残差。
--------
1 - x - x^2 ) 1 + 2 x
[
我们将残差的最低阶项(
1)除以分母的常数项(1)，然后将商放在最上面。 1
--------
1 - x - x^2 ) 1 + 2 x
现在，我们将
1 - x - x^2与1相乘，然后从当前残差中减去它。 1
--------
1 - x - x^2 ) 1 + 2 x
1 - x - x^2
-------------
3 x + x^2
再来一遍。
1 + 3 x
--------
1 - x - x^2 ) 1 + 2 x
1 - x - x^2
---------------
3 x + x^2
3 x - 3 x^2 - 3 x^3
-------------------
4 x^2 + 3 x^3
然后再次。
1 + 3 x + 4 x^2
----------------
1 - x - x^2 ) 1 + 2 x
1 - x - x^2
---------------
3 x + x^2
3 x - 3 x^2 - 3 x^3
-------------------
4 x^2 + 3 x^3
4 x^2 - 4 x^3 - 4 x^4
---------------------
7 x^3 + 4 x^4
然后再次。
1 + 3 x + 4 x^2 + 7 x^3
------------------------
1 - x - x^2 ) 1 + 2 x
1 - x - x^2
---------------
3 x + x^2
3 x - 3 x^2 - 3 x^3
-------------------
4 x^2 + 3 x^3
4 x^2 - 4 x^3 - 4 x^4
---------------------
7 x^3 + 4 x^4
7 x^3 - 7 x^4 - 7 x^4
---------------------
11 x^4 + 7 x^5
各个除法有点无聊，因为我使用了带前导
1的除数，但是如果我使用了2 - 2 x - 2 x^2，则商中的所有系数都将被2除以。