Computing Fibonacci numbers (and similarly defined functions) in log time
From MaRDI portal
Publication:1148672
DOI10.1016/0020-0190(80)90003-4zbMath0452.68052OpenAlexW2016227901MaRDI QIDQ1148672
Publication date: 1980
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(80)90003-4
Analysis of algorithms and problem complexity (68Q25) Recurrences (11B37) Software, source code, etc. for problems pertaining to number theory (11-04)
Related Items
A chained-matrices approach for parallel computation of continued fractions and its applications ⋮ A fast algorithm for computing large Fibonacci numbers ⋮ A Formal Derivation of an 0(log n) Algorithm for Computing Fibonacci Numbers ⋮ Horner's rule and the computation of linear recurrences ⋮ On the number of arithmetical operations for finding Fibonacci numbers ⋮ Improved algorithms for the calculation of Fibonacci numbers ⋮ On the logarithmic evaluation of recurrence relations ⋮ An O(k2log(n/k)) Algorithm for Computing Generalized Order-k Fibonacci Numbers with Linear Space ⋮ 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 ⋮ Efficient computation of terms of linear recurrence sequences of any order ⋮ Fast computation of periodic continued fractions ⋮ An O(log n) algorithm for computing periodic continued fractions and its applications ⋮ Computing sums of order-k Fibonacci numbers in log time ⋮ A presentation of the Fibonacci algorithm ⋮ Polynomial modular product verification and its implications
Cites Work
