Fastest Fibonacci Algorithm

Published on in Algorithms

Introduction

In mathematics, the Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones.

By definition, the first two numbers in the Fibonacci sequence are either 1 and 1, or 0 and 1, depending on the chosen starting point of the sequence, and each subsequent number is the sum of the previous two.

The sequence Fn of Fibonacci numbers is defined by the recurrence relation:
F(n) = F(n-1) + F(n-2)

with seed values:
F(0) = 0 and
F(1) = 1

We get the following sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

Well, that's quite simple!

This is a working code and it's quite fast. Here's the asymptotic analysis for this function:

  • Time Complexity: O(n)
  • Space Complexity: O(1)

We aren't using the recursive definition of this series, so we aren't doing repeat calculations. We're calculating from bottom-up in linear time and using only constant space. But is this the fastest way to solve this problem?

Saving some more time! (a lot more)

This another O(n) which relies on the fact that if we n-times multiply the matrix M = [[1, 1], [1, 0]] to itself, in other words calculate power(M, n), then we get the (n+1)th Fibonacci number as the element at row and column [0, 0] in the resultant matrix.

The matrix representation gives the following closed expression for the Fibonacci numbers:

This method can be optimized to work in O(log n) time complexity. We can perform recursive multiplication to get the result of power(M, n).

This will run much faster! Here's the asymptotic analysis for this function:

  • Time Complexity: O(log n)
  • Space Complexity: O(log n)

It can be seen that our space complexity increased from constant to logarithmic. This is because of the stack overhead created due to recursive calls while performing matrix exponentiation.

There is another way to optimise this code further so that we have constant time. But that's a challenge for you to figure out!

Benchmarking our code

For both implementations, we'll compute 1,000,000 (one millionth) Fibonacci number and see how long it takes.

  1. Naive approach: --- 13.302024126052856 seconds ---
  2. Matrix approach: --- 0.25197505950927734 seconds ---

Bonus

Wondering what the featured image of this post have to do with the Fibonacci sequence? Read about Golden Ratio (Phi) and how it is related to the Fibonacci sequence.