11
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 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
    Commented Mar 31, 2012 at 5:52
  • 2
    $\begingroup$ I think the question is probably fine here. $\endgroup$
    – Kaveh
    Commented Mar 31, 2012 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ε
    Commented Mar 31, 2012 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
    Commented Mar 31, 2012 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
    Commented Mar 31, 2012 at 13:40

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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