Golden and Alternating, fast simple O(lg n) algorithms for Fibonacci

2010/10/31 by L. F. Johnson, Johnson, L. F.
Computer Science · Engineering · Physics and Astronomy · #Advanced Mathematical Theories and Applications #Coding theory and cryptography #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1011.0148

openalex publication_date 2010/10/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Two very fast and simple O(lg n) algorithms for individual Fibonacci numbers are given and compared to competing algorithms. A simple O(lg n) recursion is derived that can also be applied to Lucas. A formula is given to estimate the largest n, where F_n does not overflow the implementation's data type. The danger of timing runs on input that is too large for the computer representation leads to false research results.

Related

• Middle and Ripple, fast simple O(lg n) algorithms for Lucas Numbers
• Twelve Simple Algorithms to Compute Fibonacci Numbers
• A fast recurrence for Fibonacci and Lucas numbers
• Computing Fibonacci numbers on a Turing Machine
• Uniform random generations and rejection method(I) with binomial majorant