Code for Matrix Exponentiation

Can anyone please post their code for Fast Matrix Exponentiation (O(logN)) that they actually use (not the ones from some other websites)? I have been trying to code it but it becomes messy and difficult to put to use. It would be great if there are no classes involved in the code.

UPDATE: Following is the code for Matrix Exponentiation provided by @shashank5013:

`````` # define m
void multiply(int a[][m], int b[][m], int dim) {
int c[m][m];
for (int i = 0; i < dim; i++) {

for (int j = 0; j < dim; j++) {
int sum = 0;
for (int k = 0; k < dim; k++) {
sum += a[i][k] * b[k][j];
}

c[i][j] = sum;
}
}
for (int i = 0; i < dim; i++) {
for (int j = 0; j < dim; j++) {
a[i][j] = c[i][j];
}
}
}
void matrixexponentiation(int arr[][m], int dim, int power) {
int I[m][m];
for (int i = 0; i < dim; i++) {
for (int j = 0; j < dim; j++) {
if (i == j) {
I[i][j] = 1;
} else {
I[i][j] = 0;
}
}
}
while (power != 1) {
if (power % 2) {
multiply(I, arr, dim);
power--;
} else {
multiply(arr, arr, dim);
power /= 2;
}

}
multiply(arr, I, dim);
}
``````

(The decrement operation on βpowerβ has been corrected and the code has been formatted )

1 Like
``````#define m
void multiply(int a[][m],int b[][m],int dim)
{
int c[m][m];
for (int i=0;i<dim;i++)
{

for (int j=0;j<dim;j++)
{
int sum=0;
for (int k=0;k<dim;k++)
{
sum+=a[i][k]*b[k][j];
}

c[i][j]=sum;
}
}
for (int i=0;i<dim;i++)
{
for (int j=0;j<dim;j++)
{
a[i][j]=c[i][j];
}
}
}
void matrixexponentiation(int arr[][m],int dim,int power)
{
int I[m][m];
for (int i=0;i<dim;i++)
{
for (int j=0;j<dim;j++)
{
if (i==j)
{
I[i][j]=1;
}
else
{
I[i][j]=0;
}
}
}
while(power!=1)
{
if (power%2)
{
multiply(I,arr,dim);
power--;
}
else
{
multiply(arr,arr,dim);
power/=2;
}

}
multiply(arr,I,dim);

}
``````
2 Likes

In Python:

``````m=1000000007
def mul(I,l,n):
res=[[0]*n for i in range(n)]
for i in range(n):
for j in range(n):
res[i][j]=0
for k in range(n):
res[i][j]=(res[i][j]%m + ((I[i][k]%m *l[k][j]%m)%m)%m) %m

for i in range(n):
for j in range(n):
I[i][j]=(res[i][j])

def power(l,n,a):
I=[[0]*n for i in range(n)]
for i in range(n):
for j in range(n):
if i==j:
I[i][j]=1
while a:
if a%2:
mul(I,l,n)
a=a-1
else:
mul(l,l,n)
a=a//2
return I
``````
1 Like

Please take note that the given code will work for power>=1
otherwise it will give TLE