Code for Matrix Exponentiation

general
,
1

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.:slightly_smiling_face:

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

 # 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 :slightly_smiling_face: )

1 Like
2 
#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
3

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
4

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