Last active
April 17, 2019 18:27
-
-
Save monsij/0649decd28c16bca8e5fec2d3aa204f9 to your computer and use it in GitHub Desktop.
Fast matrix exponentiation with Modulo
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//These are two functions which aid in raising a matrix data[][] to the power n using fast exponentiation techniques. | |
/* | |
Prerequisites: | |
// The matrix must be a 2x2 matrix. | |
1. data[2][2] ->The matrix which is required to be raised to nth power | |
2. result[2][2] ->Initially make it equal to a 2x2 identity matrix.This matrix contains the required result. | |
3. n -> The exponent | |
4. Also include --> #define ll long long int | |
5. Also include --> #define mod_12 1000000007 | |
<--- Note-All the above variables must be global ---> | |
*/ | |
ll modulo_my(ll m, ll n) { return m >= 0 ? m % n : ( n - abs ( m%n ) ) % n; } | |
void multiply_mat(ll check) | |
{ | |
if(check==1) | |
{ | |
ll aux[2][2]; | |
for(ll i=0; i<2; i++) | |
{ | |
for(ll j=0; j<2; j++) | |
{ | |
ll temp=0; | |
for(ll k=0; k<2; k++) | |
{ | |
temp += (modulo_my((modulo_my(result[i][k],mod_12) * modulo_my(data[k][j],mod_12)),mod_12)); | |
} | |
aux[i][j]=(modulo_my(temp,mod_12)); | |
} | |
} | |
for(ll i=0; i<2; i++) | |
{ | |
for(ll j=0; j<2; j++) | |
{ | |
result[i][j] = aux[i][j]; | |
} | |
} | |
} | |
else if(check==2) | |
{ | |
ll aux[2][2]; | |
for(ll i=0; i<2; i++) | |
{ | |
for(ll j=0; j<2; j++) | |
{ | |
ll temp=0; | |
for(ll k=0; k<2; k++) | |
{ | |
temp += (modulo_my((modulo_my(data[i][k],mod_12) * modulo_my(data[k][j],mod_12)),mod_12)); | |
} | |
aux[i][j]=(modulo_my(temp,mod_12)); | |
} | |
} | |
for(ll i=0; i<2; i++) | |
{ | |
for(ll j=0; j<2; j++) | |
{ | |
data[i][j] = aux[i][j]; | |
} | |
} | |
} | |
} | |
void fast_expo() | |
{ | |
while(n) | |
{ | |
if(n&1) | |
{ | |
multiply_mat(1);//result = result * data | |
} | |
multiply_mat(2);//data = data * data | |
n >>=1; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment