Efficient computation of terms of linear recurrence sequences of any order

zbMATH Open1459.11035arXiv1610.06376MaRDI QIDQ5384249FDOQ5384249

Authors: Dmitry I. Khomovsky 

Publication date: 21 June 2019

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.

Full work available at URL: https://arxiv.org/abs/1610.06376

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

Mathematics Subject Classification ID

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

Cites Work

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

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
• An Efficient Formula for Linear Recurrences
• Efficient counting of degree sequences

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)