Efficient computation of terms of linear recurrence sequences of any order

Abstract

In this paper we give efficient algorithms for computing second-, third-, and fourth-order linear recurrences. We also present an algorithm scheme for computing terms with the indices $N,\dots ,N+n-1$ of an $n$th-order linear recurrence. Unlike Fiduccia's algorithm our approach uses certain formulas for modular polynomial squarings.

arXiv comment4 algorithms. arXiv admin note: substantial text overlap with arXiv:1610.03883

Cited by in corpus (1)

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