arXiv Open Access 2020

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

Alin Bostan Ryuhei Mori

Lihat Sumber

Abstrak

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, powering of matrices and high-order lifting.

Topik & Kata Kunci

cs.SC

Penulis (2)

Alin Bostan

Ryuhei Mori

Format Sitasi

APA MLA BibTeX

Bostan, A., Mori, R. (2020). A Simple and Fast Algorithm for Computing the $N$-th Term of a Linearly Recurrent Sequence. https://arxiv.org/abs/2008.08822

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2020
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓