Horner's rule and the computation of linear recurrences

DOI10.1016/0020-0190(87)90168-2zbMath0628.10009OpenAlexW2014476274MaRDI QIDQ1092939

Adriano Pascoletti, David Gries, Luigi Sbriz

Publication date: 1987

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90168-2

zbMATH Keywords

algorithmlinear recurrencesFibonacci numberslinear difference equationHorner's scheme

Mathematics Subject Classification ID

Recurrences (11B37) Software, source code, etc. for problems pertaining to number theory (11-04)

Cites Work

• A presentation of the Fibonacci algorithm
• Computing Fibonacci numbers (and similarly defined functions) in log time
• An \(O(\log n)\) algorithm for computing the \(n\)th element of the solution of a difference equation
• Derivation of an \(O(k^ 2\log n)\) algorithm for computing order-k Fibonacci numbers from the \(O(k^ 3\log n)\) matrix multiplication method
• Computing sums of order-k Fibonacci numbers in log time

This page was built for publication: Horner's rule and the computation of linear recurrences