In this tutorial, we will explore a C++ code to calculate Fibonacci numbers using matrices.
Calculating Fibonacci numbers using matrix exponentiation is a valuable method leveraging the power of matrices to efficiently compute Fibonacci sequences. This approach proves particularly advantageous when dealing with large Fibonacci numbers, as it significantly minimizes time complexity in contrast to conventional recursive or iterative methods.
Fibonacci Numbers:
The Fibonacci sequence represents a collection of numbers where each number is the result of adding the two preceding numbers. This sequence initiates with 0 and 1, continuing as 0, 1, 1, 2, 3, 5, 8, 13, 21, and continues infinitely. The mathematical definition of the Fibonacci sequence is as follows:
fib(0)=0, fib(1)=1
fib(n)=fib(n-1)+fib(n-2) for n>1
Matrix Exponentiation Method:
The technique of matrix exponentiation efficiently computes Fibonacci numbers by merging matrix multiplication and exponentiation. Rather than computing Fibonacci numbers iteratively, we can represent the connection between consecutive Fibonacci numbers using a matrix equation.
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)
