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

(1) , (2)
1
2
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.
Fichier principal
Vignette du fichier
BoMo21-final.pdf (595 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

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

Identifiers

  • HAL Id : hal-02917827 , version 2

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-02917827v2⟩
566 View
548 Download

Share

Gmail Facebook Twitter LinkedIn More