# 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. – Sai Venkat Mar 31 '12 at 5:52
• I think the question is probably fine here. – Kaveh Mar 31 '12 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. – Jeffε Mar 31 '12 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). – Emil Jeřábek Mar 31 '12 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). – Emil Jeřábek Mar 31 '12 at 13:40