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 .

  • 5
    $\begingroup$ 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. $\endgroup$ – Sai Venkat Mar 31 '12 at 5:52
  • 2
    $\begingroup$ I think the question is probably fine here. $\endgroup$ – Kaveh Mar 31 '12 at 6:18
  • 8
    $\begingroup$ 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. $\endgroup$ – Jeffε Mar 31 '12 at 9:38
  • 3
    $\begingroup$ 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). $\endgroup$ – Emil Jeřábek Mar 31 '12 at 13:18
  • 2
    $\begingroup$ @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). $\endgroup$ – Emil Jeřábek Mar 31 '12 at 13:40

According to this Project Nayuki link, Fast doubling is even faster than Fast Matrix, because redundant calculations are removed.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.