# 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, ll M)`
14. `{`
15. `    ll x =  F * M + F * M;`
16. `    ll y =  F * M + F * M;`
17. `    ll z =  F * M + F * M;`
18. `    ll w =  F * M + F * M;`
19. `    F = x;`
20. `    F = y;`
21. `    F = z;`
22. `    F = w;`
23. `}`
24. ` `
25. ` /* `
26. `  * function to calculate power of a matrix`
27. `  */`
28. `void power(ll F, int n)`
29. `{`
30. `    if (n == 0 || n == 1)`
31. `        return;`
32. `    ll M = {{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 = {{1,1},{1,0}};`
45. `    if (n == 0)`
46. `        return 0;`
47. `    power(F, n - 1);`
48. `    return F;`
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. 