A Simple and Fast Algorithm for Computing the <i>N</i>-th Term of a Linearly Recurrent Sequence
A Simple and Fast Algorithm for Computing the <i>N</i>-th Term of a Linearly Recurrent Sequence
复制标题
计算线性循环序列第N项的简单快速算法
DOI：
10.1137/1.9781611976496.14
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Bostan Alin and Mori Ryuhei
中科院分区：
文献类型：
--
作者：
平賀 大一;秦 俊陽;松井 崇;下田 亮;岡本 正洋;征矢 英昭;Bostan Alin and Mori Ryuhei
本文给出了一个计算给定线性递归序列第N项的简单快速算法。我们的新算法使用O（M（d）logN）个算术运算，其中是递归的阶，M（d）表示计算两个次多项式乘积的算术运算的次数。Fiduccia（1985）提出的最新算法具有相同的算术复杂度，直到常数因子。我们的算法更简单，更快，并通过一个完全不同的方法获得。我们还讨论了几个算法的应用，特别是多项式模幂和电源的矩阵。
We present a simple and fast algorithm for computing theN-th term of a given linearly recurrent sequence. Our new algorithm usesO(M(d) logN) arithmetic operations, wheredis the order of the recurrence, and M(d) denotes the number of arithmetic operations for computing the product of two polynomials of degreed. The state-of-the-art algorithm, due to Fiduccia (1985), has the same arithmetic complexity up to a constant factor. Our algorithm is simpler, faster and obtained by a totally different method. We also discuss several algorithmic applications, notably to polynomial modular exponentiation and powering of matrices.
登录
查看更多内容
在平均多项式时间内计算超椭圆曲线上的点
影响因子：
4.9
作者：
David Harvey
通讯作者：
David Harvey
规范矩阵形式的近乎最优算法
DOI：
10.1137/s0097539793252687
发表时间：
1995
期刊：
SIAM J. Comput.
影响因子：
--
作者：
M. Giesbrecht
通讯作者：
M. Giesbrecht
DOI：
10.2140/obs.2019.2.119
发表时间：
2018
期刊：
ArXiv
影响因子：
--
作者：
A. Bostan;X. Caruso;G. Christol;P. Dumas
通讯作者：
P. Dumas
关于使用非算术基元进行更快的整数计算
DOI：
10.1007/978-3-540-85194-3_11
发表时间：
2007
期刊：
SIAM Rev.
影响因子：
--
作者：
Katharina Lürwer;M. Ziegler
通讯作者：
M. Ziegler
纪念斐波那契
影响因子：
0.5
作者：
E. Dijkstra
通讯作者：
E. Dijkstra