In this article, we will discuss a C++ program to find Fibonacci numbers using Matrix.
Finding Fibonacci numbers by matrix exponentiation is an important technique that takes advantage of the strength of matrices to calculate Fibonacci sequences effectively. This strategy is very beneficial when working with huge Fibonacci numbers because it considerably reduces time complexity when compared to typical recursive or iterative approaches.
Fibonacci Numbers:
The Fibonacci sequence is a set of numbers in which each of them is the sum of the two numbers before it. The series begins with 0 and 1 and proceeds in the following order: 0, 1, 1, 2, 3, 5, 8, 13, 21 , and so on. The sequence known as Fibonacci is defined mathematically in the following manner:
fib(0)=0, fib(1)=1
fib(n)=fib(n-1)+fib(n-2) for n>1
Matrix Exponentiation Method:
The matrix exponentiation method effectively finds Fibonacci numbers by combining multiplication by a matrix and exponentiation. Instead of calculating Fibonacci numbers repeatedly, we can use a matrix equation to express the relationship between successive Fibonacci numbers.
Algorithm:
Begin
Consider two two-dimensional arrays.
Make a function and multiply the matrices
Create a new function to determine the matrix's power.
Create a function to calculate the Fibonacci number.
multiplication (array1[2][2], array2[2][2])
Consider four variables a,b,c and d:
a = array1[0][0] * array2[0][0] + array1[0][1] * array2[1][0]
b= array1[0][0] * array2[0][1] + array1[0][1] * array2[1][1]
c = array1[1][0] * array2[0][0] + array1[1][1] * array2[1][0]
d = array1[1][0] * array2[0][1] + array1[1][1] * array2[1][1]
array1[0][0] = a
array1[0][1] = b
array1[1][0] = c
array1[1][1] = d
Power(array1[2][2], taking integer num as input) if (num == 0 or num == 1) return;
arr1 [2][2] = 1,1, 1,0
power(array1, num / 2)
multiply(array1, array1)
if (num mod 2 not equal to 0)
multiply(array1, array2)
fibonacci(num)
array1[2][2] = {{1,1}, {1,0}}
if num ==0
return 0
power(array1 num - 1)
return array1[0][0]
End
Example:
//A C++ program is used to find the value of fib(n), where fib(n) is defined as // Fib(n) = Fib(n-1) + Fib(n-2) + Fib(n-3), n >= 3
// Fib(0) = 0, Fib(1) = 1, Fib(2) = 1
#include<bits/stdc++.h>
using namespace std;
// A function for multiplying two matrices
// arr[][] and brr[][]. The result of multiplication is returned to brr[][]
void multiplyMatrix(int arr[3][3], int brr[3][3])
{
// reating an auxiliary multiplier to store multiplying matrix elements
int mulx[3][3];
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
mulx[i][j] = 0;
for (int k = 0; k < 3; k++)
mulx[i][j] += arr[i][k]*brr[k][j];
}
}
// array for storing the result
for (int i=0; i<3; i++)
for (int j=0; j<3; j++)
arr[i][j] = mulx[i][j]; // matrix values are updated
}
// function to compute the power
int powerFun(int Fib[3][3], int num)
{
int Mat[3][3] = {{1,1,0}, {1,0,0}, {0,1,0}};
// declaring the initial values and then multiplying them
if (num==1)
return Fib[0][0] + Fib[0][1];
powerFun(Fib, num/2);
multiplyMatrix(Fib, Fib);
if (num%2 != 0)
multiplyMatrix(Fib, Mat);
//declaring the initial values and then multiplying them
return Fib[0][0] + Fib[0][1] ;
}
// Return the term of a sequence defined by the recurrence relation shown below.
// fib(n) has been defined as
// fib(num) = fib(num-1) + fib(num-2) + fib(num-3), num>=3
// fib(0) = 0, fib(1) = 1, fib(2) = 1
int findNthTermis(int num)
{
int Fib[3][3] = {{1,1,0}, {1,0,0}, {0,1,0}} ;
//base conditions
if(num==0)
return 0;
if(num==1 || num==2)
return 1;
return powerFun(Fib, num-2);
}
// Driver code
int main()
{
int num = 7;
cout << "Fib(7) is " << findNthTermis(num);
return 0;
}
Output:
Fib(7) is 13
Complexity:
Time Complexity: O(logN)
Auxiliary Space: O(logN)