Efficient computation of terms of linear recurrence sequences of any order

MaRDI QIDQ5384249zbMATH OpenFDO

Authors Dmitry I. Khomovsky

Publication date 21 June 2019

Full work available at URL https://arxiv.org/abs/1610.06376, http://math.colgate.edu/~integers/s39/s39.pdf

Mathematics Subject Classification ID

Recurrences (11B37) Calculation of integer sequences (11Y55)

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,ldots,N+n-1$ of an $n$th-order linear recurrence. Unlike Fiduccia's algorithm our approach uses certain formulas for modular polynomial squarings.

Recommendations

• An Efficient Formula for Linear Recurrences
• A fast algorithm for solving linearly recurrent sequences
• scientific article; zbMATH DE number 3945316
• Low complexity algorithms for linear recurrences
• scientific article; zbMATH DE number 3916360
• Linear recurring sequences for computing the resultant of multivariate polynomials
• scientific article; zbMATH DE number 4118432
• Vectorization of Linear Recurrence Relations
• On the numerical evaluation of linear recurrences

Cites work

• scientific article; zbMATH DE number 977922 (Why is no real title available?)
• scientific article; zbMATH DE number 1030971 (Why is no real title available?)
• scientific article; zbMATH DE number 3212113 (Why is no real title available?)
• scientific article; zbMATH DE number 3255816 (Why is no real title available?)
• An Algorithm for Evaluation of Remote Terms in A Linear Recurrence Sequence
• An Efficient Formula for Linear Recurrences
• Characterizing Pseudoprimes for Third-Order Linear Recurrences
• Computing Fibonacci numbers (and similarly defined functions) in log time
• Linear recursive sequences and powers of matrices
• New cube root algorithm based on the third order linear recurrence relations in finite fields
• Program. construction. International summer school
• Public-key cryptosystems based on cubic finite field extensions
• Some primality tests that eluded Lucas

Cited in

(6)

• Vectorization of Linear Recurrence Relations
• A fast algorithm for solving linearly recurrent sequences
• A New Algorithm to Compute Remote Terms in Special Types of Characteristic Sequences
• New techniques for the computation of linear recurrence coefficients
• Efficient counting of degree sequences
• An Efficient Formula for Linear Recurrences

This page was built for publication: Efficient computation of terms of linear recurrence sequences of any order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384249)