# What is the fastest algorithm for calculating nth term of Fibonacci sequence?

If we exclude methods that include precalculating of all Fibonacci numbers up to a sufficiently large number of n what would be the fastest algorithm for calculating nth term of Fibonacci sequence?

I guess that Iterative and Matrix algorithms should be faster than Analytic and Recursive algorithms, (see this paper).

On this page I have found five different algorithms. According to author the fastest is a Matrix algorithm that uses $$O(\log n)$$ arithmetic operations.

• Not really a research level question. Computer Science SO is the right place but I think if you read the paper and page you have shared you will get the answer. Mar 31, 2012 at 5:52
• I think the question is probably fine here. Mar 31, 2012 at 6:18
• That matrix algorithm uses $O(\log n)$ arithmetic operations, not $O(\log n)$ "time", unless you can multiply two $n$-digit numbers in constant time. Mar 31, 2012 at 9:38
• In terms of bit complexity, recursive algorithms which go from $n$ to $2n$ in each step (such as here: gmplib.org/manual/Fibonacci-Numbers-Algorithm.html) take time $O(M(n))$, where $M(n)$ is the time needed for multiplication of two $n$-bit integers (the current best bound is $M(n)=n\,\log n\,2^{O(\log^*n)}$ by Fürer). I can't imagine you could do better (up to a multiplicative constant). Mar 31, 2012 at 13:18
• @pedja: Note that the complexity estimates they give for 3A and 3B have one $\log n$ factor too many (they apparently didn't realize that the times spent in each of the $\log n$ iterations make roughly a geometric series). Mar 31, 2012 at 13:40