Fibonacci Sequence – A complete guide

Hello guys, welcome back to “code with asharam”. In this post, I am going to introduce you to basic and advanced concepts of Fibonacci Sequence. I will be discussing the various approaches you can choose to find the nth term of Fibonacci Sequence. This post is for complete beginners and do not require any prior knowledge of anything except some of the basic concepts of Matrices multiplication and quadratic equation. So, without any further delay, let’s take a dive into deep and beautiful oceans of Fibonacci sequences.
Please grab a cup of coffee or something because this is going to be long.

Definition

It is a sequence of non-negative integers whose nth term, i.e., Fn is given by sum of last 2 terms, i.e., Fn-1+Fn-2. Base cases for this recursive relation is F0 = 0 and F1 = 1. What is so fascinating about Fibonacci Sequence is that it appears everywhere unexpectedly. You can find it in nature, in culture and in Mathematics. It occurs so frequently that there are multiple books dedicated only to Fibonacci Sequence. That’s why it becomes important for us to study Fibonacci and find efficient ways to compute its general term. So, let’s get started.

Fibonacci Sequence in O(2n)

This is the brute force method to solve this problem. We will directly use the recursive relation used in definition to compute any general term of the sequence.

fib(n) = 0 if n=0,
         1 if n=1,
         fib(n-1) + fib(n-2) otherwise

But there is a catch in this approach. If you try to find the value of fib(5) using above relation, then, you will obtain following recursion tree:

                          fib(5)
                     /             \
               fib(4)                fib(3)
             /      \                /     \
         fib(3)      fib(2)         fib(2)    fib(1)
        /     \        /    \       /    \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \
fib(1) fib(0)

Observe carefully that in each step the number of function calls are increasing by a factor of 2. So, if we try to compute fib(n), then the number of function calls will be more than 2n and that’s why this algorithm will run in O(2n) time which is a nightmare for every competitive programmer. So, there is a need to find some efficient method to compute values of such an important sequence.

Fibonacci Sequence in O(n)

Think for some time and a simple intuition will tell you to start solving the problem from base cases instead of directly approaching from fib(n). Since you already know fib(0) and fib(1), you can compute fib(2). And now since you know fib(1) and fib(2), you can compute fib(3). And so on you can go till fib(n).

def fib(n):
    store[n+1] // to store values of Fibonacci Sequence
    store[0] = 0
    store[1] = 1
    for i in [2, n]:
       store[i] = store[i-1] + store[i-2]
    return store[n]

Above algorithm takes O(n) time and also have O(n) space complexity. Generally, O(n) space complexity is not that bad but it will be pretty bad for Fibonacci. I will tell you the reason for this in then end of this article. Until then just remember that we have to solve this problem in O(1) space somehow. In the above approach, to find the value of store[i], we need to know only store[i-1], store[i-2] and not other lower values which are stored in store[]. Hence, only two variables is enough to store whole information. Let’s see how?

def fib(n):
    last = 0
    current = 1
    for i in [2, n]:
       temp = current
       current := current + last
       last = temp
    if n==0:
       return 0
    else:
       return current

So, in this method, you saw that we converted our exponential time solution to the linear time solution without even changing our recursion relation. What you were doing is called dynamic Programming which I have discussed in detail in my tutorials on Dynamic Programming.

Fibonacci Sequence in O(log2n) using Matrix exponential

Matrix exponential!!?? Such a heavy Mathematical term. But don’t worry. We are not getting into deep mathematical details. You just need to know how to multiply 2 matrices to understand this method. So, let’s see how can we use simple matrix multiplication to compute Fibonacci sequence in efficient time.

Fk+1  = 1*Fk + 1*Fk-1
Fk   = 1*Fk + 0*Fk-1

Observe carefully!!!

|Fk+1|   =   | 1 1 | * |Fk  |
|Fk  |       | 1 0 |   |Fk-1|

Denote first matrix in above equation by Ak, third matrix by Ak-1 and second matrix by C

             Ak  = C*Ak-1
**Similarly, Ak-1 = C*Ak-2             
               .
               .
             A1 = C*A0
If we combine above equation, then, we will see that
             Ak = Ck*A0

Also We know that A0 consist of 1 and 0. We can calculate power of a Matrix like we do it for integers in log2n time. That’s why, we can compute Ak and consecutively Fk in log2n time. Since this approach involved exponentiation of matrices, this technique is called matrix exponential. It is great topic and I will discuss it in future articles. Now let’s move to our final method to solve Fibonacci Sequence.

Golden ratio and Fibonacci in O(log2n)

I will quote the definition of golden ratio from Wikipedia – “Ratio of two real numbers a and b is said to be in golden ratio if ratio of a and b is equal to ratio of a+b to max(a, b)”. Let’s analyze this statement mathematically:

suppose a>b
=> a/b = (a+b)/a
=> a2 - a*b - b2 = 0
=> (a/b)2 - (a/b) - 1 = 0 (divide by b2)
Replace a/b with x
=> x2 - x - 1 = 0
This implies that a/b is the positive root of of above quadratic equation.

Hence, a/b is golden ratio and is equal to (root(5)+1)/2 = 1.1680339887....

From now on, I will use G to denote golden ratio and G’ to denote the complementary root of the quadratic equation we discussed before. Until now, you must we wondering why we are learning about golden ratio? What does Fibonacci Sequence and such an ugly looking ratio have in common. Let me answer your doubts.

G is a root of x2 - x - 1 = 0,
=> G2 = G + 1
multiply by Gk-2 on both sides, we get
=>Gk = Gk-1 + Gk-2
You can see that G0, G1, G2.....Gk forms a Fibonacci like sequence whose 
general term is defined by the relation above.
Similarly (G')0, (G')1, (G')2.....(G')k forms a Fibonacci like sequence whose
general term is defined by (G')k = (G')k-1 + (G')k-2

Now, we are almost ready to see the application of golden ratio in finding Fibonacci Sequence. But before that I will state two points which will help us in our feature endeavours.

  1. A Fibonacci like Sequence is defined uniquely by its first two terms only because all other terms ultimately depends on the first 2 terms.
  2. If Sk and S’k are general terms of 2 Fibonacci like sequences, then, p*Sk+q*S’k will be the general term of another Fibonacci like sequence. You can verify this relation by just putting values. If you want to go in details of why this statement is true, then, I will advice you to study some basics of linear algebra.
  3. Using point 2, we can generate a new Fibonacci like sequence from Gk and (G’)k. Now, if we generate a sequence such that there first 2 terms are 0 and 1, then, we will be able to generate original Fibonacci Sequence.
F0 = 0 = p*G0 + q*(G')0
F1 = 1 = p*G1 + q*(G')1
Solve these 2 equations and you will get
p = 1/root(5) and q = -1/root(5)

Hence, Fk = (Gk - (G')k)/root(5)

So, now finding Fk boils down to finding Gk and (G’)k) which can be easily done in log2k time. This method requires accurate floating point calculations which is not possible for large integers. Personally, I found this method really beautiful because it combine such different things together.
We have completed all the approaches. Now, it’s time to write code for all of them.

CODE

#include <bits/stdc++.h>
using namespace std;

// Brute Force exponential
int bruteForce(int n) {
    if (n==0) return 0;
    if (n==1) return 1;
    
    return bruteForce(n-1)+bruteForce(n-2);
}

// O(n) time and space 
int fibLinear(int n) {
    int store[n+1];
    store[0] = 0, store[1] = 1;
    
    for (int i=2; i<=n; i++) {
        store[i] = store[i-1] + store[i-2];
    }
    return store[n];
}

// O(n) time and O(1) space
int fibLinear2(int n) {
    int last = 0, current = 1;
    for (int i=2; i<=n; i++) {
        int temp = current;
        current += last;
        last = temp;
    }
    if (n==0) return 0;
    return current;
}

void multiply(int F[2][2], int M[2][2]) 
{ 
    int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0]; 
    int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1]; 
    int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0]; 
    int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1]; 
  
    F[0][0] = x; 
    F[0][1] = y; 
    F[1][0] = z; 
    F[1][1] = w; 
} 

// Matrix exponential technique
// Code taken from GeeksforgGeeks
void power(int F[2][2], int n) 
{ 
    if( n == 0 || n == 1) 
        return; 
    int M[2][2] = {{1,1},{1,0}}; 
  
    power(F, n/2); 
    multiply(F, F); 
  
    if (n%2 != 0) 
        multiply(F, M); 
} 

int fibMatrix(int n) {
    int F[2][2] = {{1,1},{1,0}}; 
    if (n == 0) 
        return 0; 
    power(F, n-1); 
    return F[0][0];
}

// Golden Ratio Method
int fibGoldenRatio(int n) {
    double g1 = (1+sqrt(5))/2;
    double g2 = (1-sqrt(5))/2;
    
    return round((pow(g1, n)-pow(g2, n))/sqrt(5));
}

int main() {
   
    cout << bruteForce(8) << endl;
    cout << fibLinear(8) << endl;
    cout << fibLinear(8) << endl; 
    cout << fibMatrix(8) << endl;
    cout <<	fibGoldenRatio(8) << endl;
    // output is 5 
    
    return 0;
}

Why can’t you have O(n) space?

One thing we have to see is the growth rate of Fibonacci sequence. If you carefully observe the golden ratio formula, then, you will see that the term containing G increases exponentially and term containing G’ is very very small compared to the G term. Hence, you can say that Fibonacci sequence increase exponentially. Even the thousandth term of Fibonacci Sequence have 209 digits.
Storing such large integers will take a large amount of memory. Also, as size of numbers increases, we can no longer consider addition and multiplication an O(1) operation. This is why even our time complexity analysis will not give accurate results for larger Fibonacci terms. Therefore, In contests, you are given to find modulus of the terms with respect to some prime number.
So, that’s it guys for today. I hope you would have enjoyed this tutorial. If you liked this tutorial, then, please follow my blog and share it with your friends.
You can subscribe to my YouTube channel for video tutorials on competitive programming.
You can connect with me on LinkedIn. To get all of your queries answered, you can message me on Quora. Follow me on medium for more of my writings.

Leave a Reply

%d bloggers like this: