Skip to Main content Skip to Navigation
Conference papers

A Simple and Fast Algorithm for Computing the $N$-th Term of a Linearly Recurrent Sequence

Abstract : We present a simple and fast algorithm for computing the $N$-th term of a given linearly recurrent sequence. Our new algorithm uses $O(\mathsf{M}(d) \log N)$ arithmetic operations, where $d$ is the order of the recurrence, and $\mathsf{M}(d)$ denotes the number of arithmetic operations for computing the product of two polynomials of degree $d$. The state-of-the-art algorithm, due to Charles 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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-02917827
Contributor : Alin Bostan <>
Submitted on : Monday, December 21, 2020 - 4:02:12 PM
Last modification on : Tuesday, December 22, 2020 - 3:35:26 AM

File

BoMo21-final.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02917827, version 2

Collections

Citation

Alin Bostan, Ryuhei Mori. A Simple and Fast Algorithm for Computing the $N$-th Term of a Linearly Recurrent Sequence. SOSA'21 (SIAM Symposium on Simplicity in Algorithms), Jan 2021, Alexandria, United States. ⟨hal-02917827v2⟩

Share

Metrics

Record views

37

Files downloads

141