An Efficient Formula for Linear Recurrences

DOI10.1137/0214007zbMath0561.68033OpenAlexW2007463894MaRDI QIDQ5186731

Charles M. Fiduccia

Publication date: 1985

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0214007

zbMATH Keywords

fast algorithmsdifference equationsrecurrence relationlinear recurrencesparallel algorithmsalgebraic complexitycompanion matricesfast polynomial multiplicationpolynomial arithmetic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Related Items

Algebraic complexity of computing polynomial zeros, On the number of arithmetical operations for finding Fibonacci numbers, Sparse approaches for the exact distribution of patterns in long state sequences generated by a Markov source, Fast computation of the \(N\)-th term of a \(q\)-holonomic sequence and applications, Beating binary powering for polynomial matrices, Fast coefficient computation for algebraic power series in positive characteristic, On Faster Integer Calculations Using Non-arithmetic Primitives, A combinatorial construction of high order algorithms for finding polynomial roots of known multiplicity, New recombination algorithms for bivariate polynomial factorization based on Hensel lifting, Weak minimization of DFA -- an algorithm and applications, Fast algorithms for the Sylvester equation \(AX-XB^{T}=C\), Efficient computation of terms of linear recurrence sequences of any order, Substitutions for linear shift register sequences and the factorization algorithms of Berlekamp and Niederreiter, Message transmission for GH-public key cryptosystem