Note: It is recommended to read our previous article on Binary Exponentiation, as we will be using concept of binary exponentiation in this article. If you have not yet read it click here to read it.
So, after reading our previous article lets continue with our next article
on Matrix Exponentiation.
1. So, What is Matrix Exponentiation ?
Matrix Exponentiation is basically calculating powers of a matrix
efficiently, yes you read it right we will be calculating powers of matrix
efficiently.
In simple words you are given a matrix ‘A’ and an integer ‘N’ and we need
to calculate AN. (Note A is a 2d-array or matrix here)
So, As always we think of a naïve approach (Brute force) first and then we
will optimize it with some cool observations.
2. Naïve Approach
In this we will do multiplication of matrix with itself ‘N’ times as we do
normal matrix multiplication.
Solution for naïve approach is left to you, we know you can code it. Just
go on we are always with you 😊
Time Complexity: O(M3 * N)
here M is order of matrix.
3. Matrix Exponentiation
So, here comes our real hero for this article, yeah !! Matrix
Exponentiation is here to improve time complexity of naïve approach.
Idea behind matrix exponentiation is very simple we will be just as we were
calculating an in our previous article we will calculate A N here.
Algorithm for Matrix exponentiation:
Step1:
Iterate till n > 0
Step2:
In each iteration we will check if our power (i.e. N) is even then we will multiply matrix with itself and do N = N / 2 .
Step3:
else we will multiply matrix with identity matrix and do N = N – 1
Below is the implementation of optimized approach:
Time Complexity: O( M3 * Log(n) )
It is always better to solve a question after you learn a new concept as it
helps in making concrete concepts.
So, below are problems which are handpicked by Programmers Army to make your concept more solid which you learned.
1. Problem from SPOJ: https://www.spoj.com/problems/MPOW/
2. Problem from CodeChef: https://www.codechef.com/problems/ CBARS
We highly recommend to solve above problems if you got stuck read editorials for guidance.
So that’s it for this article we will be coming up with our next article on further topics of number theory very soon till then keep learning, keep coding, keep reading and keep improving !!
Happy Coding
By Programmers Army
😊