常系数齐次线性递推
简介
常系数齐次线性递推数列(又称为 C-finite 或 C-recursive 数列)是常见的一类基础的递推数列。
对于数列
其中
这里
Fiduccia 算法
Fiduccia 算法使用多项式取模和快速幂来计算
算法:构造多项式
其中定义
证明:我们定义
我们定义多项式
观察到
且
我们将这个递推用矩阵表示有
可知
表示为有理函数
对于上述数列
且
证明:对于
我们只需要令
那么根据
Bostan–Mori 算法
计算单项
我们的目标仍然是给出上述多项式
Bostan–Mori 算法基于 Graeffe 迭代,对于上述多项式
因为分母
我们付出两次多项式乘法的代价使得问题至少减少为原先的一半,而当
计算连续若干项
目标是给出上述多项式
我们不妨假设
我们先考虑更简单的问题:
我们需要求出
就可以还原出
上面的算法虽然已经可以工作,但是每一次的递归的时间复杂度与
我们需要求出
那么对于
这是因为
我们知道
这样我们可以写出伪代码
但是只有这个算法还不够,我们需要重新找到一个有理函数并求算更多系数。
找到新的有理函数表示
我们知道
具体的,考虑
我们现在希望将递推前进
我们先用一次
最后我们使用形式幂级数的除法计算出
参考文献
- Alin Bostan, Ryuhei Mori.A Simple and Fast Algorithm for Computing the
-th Term of a Linearly Recurrent Sequence.
本页面最近更新:2024/9/29 23:31:19,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:hly1204, Enter-tainer, ksyx, ouuan, QAQAutoMaton, shuzhouliu, thredreams, Tiphereth-A
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用