Fast Computation of Fibonacci Numbers and Their Sums
M. C. Er · Journal of Information and Optimization Sciences · 1985
A fast algorithm for computing Fibonacci numbers and their sums is presented. The running time of the algorithm is (3 log n) multiplicative and n additive operations for large and small n respectively. The theoretical basis for doing so is also discussed.