Middle and Ripple, fast simple O(lg n) algorithms for Lucas Numbers

2010/12/01 by L. F. Johnson, Johnson, L. F.
Mathematics · Physics and Astronomy · #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Advanced Mathematical Theories and Applications #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT)

paper · pdf · doi:10.48550/arxiv.1012.0284

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

Abstract

A fast simple O(log n) iteration algorithm for individual Lucas numbers is given. This is faster than using Fibonacci based methods because of the structure of Lucas numbers. Using a sqrt 5 conversion factor on Lucus numbers gives a faster Fibonacci algorithm. In addition, a fast simple recursive algorithm for individual Lucas numbers is given that is O(log n).

Related

• Golden and Alternating, fast simple O(lg n) algorithms for Fibonacci
• A fast recurrence for Fibonacci and Lucas numbers
• Twelve Simple Algorithms to Compute Fibonacci Numbers
• Recurrence relations and fast algorithms
• Some results on average of Fibonacci and Lucas sequences