Computing sums of order-k Fibonacci numbers in log time
From MaRDI portal
Publication:1838317
DOI10.1016/0020-0190(83)90082-0zbMath0509.68064OpenAlexW1968716101MaRDI QIDQ1838317
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
Analysis of algorithms and problem complexity (68Q25) Radix representation; digital problems (11A63) Discrete mathematics in relation to computer science (68R99)
Related Items (5)
A fast algorithm for computing large Fibonacci numbers ⋮ Horner's rule and the computation of linear recurrences ⋮ Fast computation of solutions of linear difference equations by Er's rule ⋮ On the computing of the generalized order-\(k\) Pell numbers in log time ⋮ The generalized order-\(k\) Fibonacci-Pell sequence by matrix methods
Cites Work
- An O(log n) algorithm for computing general order-k Fibonacci numbers
- 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
This page was built for publication: Computing sums of order-k Fibonacci numbers in log time
