Fibonacci numbers

Sneha Mallik
Last Updated: May 13, 2022

Introduction 

 

The fibonacci series is the number sequence in which the given number results from adding the two previous numbers. The terms in the Fibonacci sequence are as follows:

The individual numbers in this sequence are called Fibonacci numbers. The Fibonacci sequence is a fantastic mathematical concept found in various places, including seashell patterns and the Parthenon.

Properties of Fibonacci Numbers

  • The ADDITION Rule

FN + K = FK . FN + 1 + FK - 1 . FN

  • Applying Addition Rule to the case, K = N

FN + N = FN . FN + 1 + FN - 1 . FN

          F2N = FN ( FN + 1 + FN - 1)

  • From the above property, we can prove that for any positive integer K, FNK is the multiple of F(By the Induction Hypothesis). 
  • The inverse of the above property is true since, if FM is multiple of FN, then M is also the multiple of N.
  • Cassini’s Identity

FN - 1 . FN + 1 - FN2 = (-1)N

This identity was given by Giovanni Domenico Cassini, an Italian mathematician. In the mathematical expression, N is the variable and it can have values from 1…..N.

For eg., if ‘N’ is an odd number, i.e. 1, 3, 5,... then (-1)N+1 = +1 in every case. But if we take even value here, we will get the result as -1.

  • GCD Identity

For M, N >= 1

GCD(FM , FN) = FGCD (M, N) , where M, N are integers

The Golden Ratio Approach

The golden ratio is defined as the limit of the ratio of successive terms in the Fibonacci sequence.

Now, if we divide Fwith F1, we get,

F2 / F1 = 1 / 1 = 1

F3 / F2 = 2 / 1 = 2

F4 / F3 = 3 / 2 = 1.5

F5 / F4 = 5 / 3 = 1.667

F6 / F5 = 8 / 5 = 1.6

F7 / F6 = 13 / 8 = 1.625

F8 / F7 = 21 / 13 = 1.61538

F9 / F8 = 34 / 21 = 1.619047

F10 / F9 = 55 / 34 = 1.61765

F11 / F10 = 89 / 55 = 1.61818

F12 / F11 = 144 / 89 = 1.617975

F13 / F12 = 233 / 144 = 1.61805

.

.

.

and so on.

 

The golden ratio is coming about 1.618, as it means that as ‘N’ becomes sufficiently large, the fibonacci sequence approaches or approximates a geometric sequence. So, starting at number 144, and if we multiply 144 by 1.618, we get 233 (Approx.), the next element in the sequence. If we now multiply 233 with 1.618, we get approximately 377. Hence this golden ratio helps to approximate the next number in the series easily.

The formula for golden ratio is,

                                                          (1 + √5) - (1 - √5)N

FN = ------------------------------

                       2N . √5

 

For example, let us find out the 8th element in the sequence using the formula,

 

          (1 + √5) - (1 - √5)8

F8 = ------------------------------ = 21

                       28 . √5

Code:

// To print the Nth Fibonacci Number.
#include <bits/stdc++.h>
using namespace std;

// The approx value of the golden ratio approach
double goldenRatio = 1.6180339;

// Taking an array of size, 'N' = 5
int fibonacciSeries[5] = {01123};

// The function to find Nth fibonacci number
int fibonacci(int N){
    
    // The fibonacci no.s for N < 5
    if(N < 5)
        return fibonacciSeries[N];

    // Or else to start counting from the 4th term
    int i = 4, func = 4;
    while(i < N){
        func = round(func * goldenRatio);
        i++;
    }
    return func;


// Main program
int main(){
    int N = 10;
    cout << N << "th Fibonacci number in the series: " << fibonacci(N) 
    << endl;
    return 0;
}

 

Output:

10th Fibonacci number in the series: 68

 

The matrix multiplication in O(log N)

Code of Fibonacci Number Matrix Multiplication in C++

// To find the Nth Fibonacci Number in O(log N) time complexity

#include <bits/stdc++.h>
using namespace std
#define int long long
const int N = 1e52;
const int mod = 1e97;

// Function to multiply two square matrices
vector<vector<int> > multiply(vector<vector<int>> &A, vector<vector<int> > &B){
    int t = A.size();
    vector<vector<int> > ans(t, vector<int>(t, 0));
    for(int i = 0; i < t; i++){
        for(int j = 0; j < t; j++){
            for(int k = 0; k < t; k++){
                ans[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return ans;
}

// Function for matrix exponentiation
vector<vector<int> > matrixMultiplication(vector<vector<int> > &V, int N){
    if(N == 0){
        int t = V.size();
        vector<vector<int> > ans(t, vector<int>(t, 0));
        for(int i = 0; i < t; i++){
            ans[i][i] = 1;
        }
        return ans;
    }
    if(N == 1){
        return V;
    }
    vector<vector<int> > temp = matrixMultiplication(V, N/2);
    vector<vector<int> > ans = multiply(temp, temp);
    if(N & 1){
        ans = multiply(ans, V);
    }
    return ans;
}

signed main(){
    int N;
    cout << "Enter the Nth position to find the matrix exponentiation: 

    ";
    cin >> N;
    vector<vector<int> > V(2vector<int>(20));
    V[0][0] = V[0][1] = V[1][0] = 1;
    V[1][1] = 0;
    vector<vector<int> > ans = matrixMultiplication(V, N);
    int t = ans.size();
    for(int i = 0; i < t; i++){
        for(int j = 0; j < t; j++){
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
}

 

Input:

Enter the Nth position to find the matrix exponentiation: 7

 

Output:

21 13 
13 8 

 

Time Complexity 

The time complexity depends on two factors:

  • Matrix multiplication, K3

As the matrix moves ‘column by column’ or ‘row by row’, we will get a matrix K x K where ‘K’ represents the number of states. We can notice that in our code, the function ‘multiply’ has three nested for loops which takes time complexity = K x K x K =  K3.

  • Log(N)

For computing the large input, we raise the matrix to the power N, which takes log(N) time. 

Hence, multiplying both the factors (1) and (2), we get => K3. log(N)

Therefore, the time complexity will be O(K3 log N).

Space Complexity 

The space complexity is O(log N) since we raise the matrix to the Nth power. Hence it will take O(log N) additional space.

 

Frequently Asked Questions

What is the golden ratio in the Fibonacci sequence?

From atoms to the massive stars in the sky has patterns. The golden ratio reveals predictable or observable patterns. This ratio is derived from the Fibonacci sequence, named after Leonardo Fibonacci, an Italian mathematician.

What is the time complexity of finding the Nth fibonacci term by recursion?

The time complexity by recursion is O(2N).

 

What is the time complexity of finding Nth fibonacci term with DP?

For finding the Nth fibonacci number, we got O(N) time complexity in the dynamic programming method.

Here, we store the previous terms, which are overlapping to reduce the time complexity.

 

Key Takeaways

 

In this blog, we learned about Fibonacci numbers, their properties, the working of matrix multiplication in O(log N) time complexity, and the golden ratio approach.

Try problems related to the Fibonacci numbers here on CodeStudio to understand the working concept of Fibonacci numbers. To be more confident in data structures and algorithms, try out our DS and Algo Course.

CREDITS: GIPHY

 

By Sneha Mallik

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think