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)
Press return to continue

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

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

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.