Computing sums of order-k Fibonacci numbers in log time

DOI10.1016/0020-0190(83)90082-0MaRDI QIDQ1838317zbMATH OpenOpenAlexFDO

Authors M. C. Er

Publication date 1983

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

Full work available at URL https://doi.org/10.1016/0020-0190(83)90082-0

zbMATH Keywords

algorithmFibonacci numbersmatrix method

Mathematics Subject Classification ID

Radix representation; digital problems (11A63) Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Cites work

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

Cited in

(5)

• Horner's rule and the computation of linear recurrences
• Fast computation of solutions of linear difference equations by Er's rule
• The generalized order-\(k\) Fibonacci-Pell sequence by matrix methods
• A fast algorithm for computing large Fibonacci numbers
• On the computing of the generalized order-k Pell numbers in log time

This page was built for publication: Computing sums of order-k Fibonacci numbers in log time

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