C++ Program to Find Fibonacci Numbers using Matrix Exponentiation

This C++ Program demonstrates the the computation of Fibonacci Numbers using Matrix Exponentiation.

Here is source code of the C++ Program to Find Fibonacci Numbers using Matrix Exponentiation. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/* 
```

 * C++ Program to Find Fibonacci Numbers using Matrix Exponentiation

```
 */
```
```
#include <cstring>
```
```
#include <iostream>
```
```
#include <cstdlib>
```
```
#define ll long long
```
```
using namespace std;
```
```
 
```
```
/* 
```
```
 * function to multiply two matrices
```
```
 */
```
```
void multiply(ll F[2][2], ll M[2][2])
```
```
{
```

    ll x =  F[0][0] * M[0][0] + F[0][1] * M[1][0];

    ll y =  F[0][0] * M[0][1] + F[0][1] * M[1][1];

    ll z =  F[1][0] * M[0][0] + F[1][1] * M[1][0];

    ll 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;
```
```
}
```
```
 
```
```
 /* 
```

  * function to calculate power of a matrix

```
  */
```
```
void power(ll F[2][2], int n)
```
```
{
```
```
    if (n == 0 || n == 1)
```
```
        return;
```
```
    ll M[2][2] = {{1,1},{1,0}};
```
```
    power(F, n / 2);
```
```
    multiply(F, F);
```
```
    if (n % 2 != 0)
```
```
        multiply(F, M);
```
```
}
```
```
 
```
```
/* 
```

 * function that returns nth Fibonacci number

```
 */
```
```
ll fibo_matrix(ll n)
```
```
{
```
```
    ll F[2][2] = {{1,1},{1,0}};
```
```
    if (n == 0)
```
```
        return 0;
```
```
    power(F, n - 1);
```
```
    return F[0][0];
```
```
}
```
```
/* 
```
```
 * Main
```
```
 */
```
```
int main()
```
```
{
```
```
    int n;
```
```
    while (1)
```
```
    {
```

        cout<<"Enter the integer n to find nth fibonnaci no.(0 to exit): ";

```
        cin>>n;
```
```
        if (n == 0)
```
```
            break;
```
```
        cout<<fibo_matrix(n)<<endl;
```
```
    }
```
```
    return 0;
```
```
}
```

$ g++ fibo_matrix.cpp
$ a.out
 
Enter the integer n to find nth fibonnaci no.(0 to exit): 1
1
Enter the integer n to find nth fibonnaci no.(0 to exit): 2
1
Enter the integer n to find nth fibonnaci no.(0 to exit): 3
2
Enter the integer n to find nth fibonnaci no.(0 to exit): 4
3
Enter the integer n to find nth fibonnaci no.(0 to exit): 5
5
Enter the integer n to find nth fibonnaci no.(0 to exit): 6
8
Enter the integer n to find nth fibonnaci no.(0 to exit): 7
13
Enter the integer n to find nth fibonnaci no.(0 to exit): 8
21
Enter the integer n to find nth fibonnaci no.(0 to exit): 9
34
Enter the integer n to find nth fibonnaci no.(0 to exit): 10
55
Enter the integer n to find nth fibonnaci no.(0 to exit): 0
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

If you wish to look at all C++ Programming examples, go to C++ Programs.

If you find any mistake above, kindly email to [email protected]

« Prev - C++ Program to Find Fibonacci Numbers using Iteration

» Next - C++ Program to Find Fibonacci Numbers using Recursion

Related Posts:

Recommended Articles: