<p>According to <a href="https://www.nayuki.io/page/fast-fibonacci-algorithms" rel="noreferrer">this Project Nayuki link</a>, Fast doubling is even faster than Fast Matrix, because redundant calculations are removed.</p>

CC BY-SA 4.0
2018-10-10T15:24:53.703Z
2018-11-09T16:20:00.480Z
2018-11-09T16:20:00.480Z
G. Lu
<p>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?</p>
<p>I guess that Iterative and Matrix algorithms should be faster than Analytic and Recursive algorithms, (see <a href="http://pages.cs.wisc.edu/%7Emhock/SSL/fibcalc.pdf" rel="nofollow noreferrer">this paper</a>).</p>
<p>On <a href="http://www.ics.uci.edu/%7Eeppstein/161/960109.html" rel="nofollow noreferrer">this page</a> I have found five different algorithms. According to author the fastest is a Matrix algorithm that uses <span class="math-container">$O(\log n)$</span> arithmetic operations.</p>

CC BY-SA 3.0
2012-03-31T05:52:09.417Z
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
CC BY-SA 3.0
2012-03-31T06:18:48.823Z
I think the question is probably fine here.
Kaveh
CC BY-SA 3.0
2012-03-31T09:38:29.387Z
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ε
CC BY-SA 3.0
2012-03-31T13:18:56.120Z
In terms of bit complexity, recursive algorithms which go from $n$ to $2n$ in each step (such as here: http://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
CC BY-SA 3.0
2012-03-31T13:27:23.553Z
I suppose the matrix powering algorithm is a different formulation of the same thing.
Emil Jeřábek
CC BY-SA 3.0
2012-03-31T13:31:13.117Z
@EmilJeřábek Thanks..I have found this one :    [3B fast recursion](http://cubbi.com/fibonacci.html) algorithm .
Pedja
CC BY-SA 3.0
2012-03-31T13:40:44.813Z
@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
<ds.algorithms>
What is the fastest algorithm for calculating nth term of Fibonacci sequence?
Pedja
# What is the fastest algorithm for calculating nth term of Fibonacci sequence?

(Asked by: username_0 on 2012-03-31)

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](http://pages.cs.wisc.edu/%7Emhock/SSL/fibcalc.pdf)).

On [this page](http://www.ics.uci.edu/%7Eeppstein/161/960109.html) I have found five different algorithms. According to author the fastest is a Matrix algorithm that uses $O(\log n)$ arithmetic operations.

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: 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.  
> **username_2**: I think the question is probably fine here.  
> **username_3**: 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.  
> **username_4**: In terms of bit complexity, recursive algorithms which go from $n$ to $2n$ in each step (such as here: http://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).  
> **username_4**: I suppose the matrix powering algorithm is a different formulation of the same thing.  
> **username_0**: @EmilJeřábek Thanks..I have found this one :    [3B fast recursion](http://cubbi.com/fibonacci.html) algorithm .  
> **username_4**: @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).  

---

## 1 answers

### Answer by username_5 on 2018-10-10. Score: 6

According to [this Project Nayuki link](https://www.nayuki.io/page/fast-fibonacci-algorithms), Fast doubling is even faster than Fast Matrix, because redundant calculations are removed.


---

