# 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.

1. /*
2.  * C++ Program to Find Fibonacci Numbers using Matrix Exponentiation
3.  */
4. #include <cstring>
5. #include <iostream>
6. #include <cstdlib>
7. #define ll long long
8. using namespace std;
9.
10. /*
11.  * function to multiply two matrices
12.  */
13. void multiply(ll F[2][2], ll M[2][2])
14. {
15.     ll x =  F[0][0] * M[0][0] + F[0][1] * M[1][0];
16.     ll y =  F[0][0] * M[0][1] + F[0][1] * M[1][1];
17.     ll z =  F[1][0] * M[0][0] + F[1][1] * M[1][0];
18.     ll w =  F[1][0] * M[0][1] + F[1][1] * M[1][1];
19.     F[0][0] = x;
20.     F[0][1] = y;
21.     F[1][0] = z;
22.     F[1][1] = w;
23. }
24.
25.  /*
26.   * function to calculate power of a matrix
27.   */
28. void power(ll F[2][2], int n)
29. {
30.     if (n == 0 || n == 1)
31.         return;
32.     ll M[2][2] = {{1,1},{1,0}};
33.     power(F, n / 2);
34.     multiply(F, F);
35.     if (n % 2 != 0)
36.         multiply(F, M);
37. }
38.
39. /*
40.  * function that returns nth Fibonacci number
41.  */
42. ll fibo_matrix(ll n)
43. {
44.     ll F[2][2] = {{1,1},{1,0}};
45.     if (n == 0)
46.         return 0;
47.     power(F, n - 1);
48.     return F[0][0];
49. }
50. /*
51.  * Main
52.  */
53. int main()
54. {
55.     int n;
56.     while (1)
57.     {
58.         cout<<"Enter the integer n to find nth fibonnaci no.(0 to exit): ";
59.         cin>>n;
60.         if (n == 0)
61.             break;
62.         cout<<fibo_matrix(n)<<endl;
63.     }
64.     return 0;
65. }

\$ 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)

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