A Simple and Fast Algorithm for Computing the $N$-th Term of a Linearly Recurrent Sequence - Archive ouverte HAL Access content directly
Conference Papers Year :

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

Alin Bostan
• Function : Author
• PersonId : 831654
Ryuhei Mori
• Function : Author
• PersonId : 1075786

#### 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.

#### Domains

Computer Science [cs] Symbolic Computation [cs.SC]

### Dates and versions

hal-02917827 , version 1 (19-08-2020)
hal-02917827 , version 2 (21-12-2020)

### Identifiers

• HAL Id : hal-02917827 , version 1

### Cite

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-02917827v1⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite
569 View