Showing posts with label Modular Arithmetic. Show all posts
Showing posts with label Modular Arithmetic. Show all posts

Tuesday, October 15, 2013

Matrix Exponentiation

Learning resource:
Fast exponentiation of numbers: http://machlearner.blogspot.in/2013/09/modular-exponentiation.html

Same concept can be applied to raise matrices to a power.

Implementation:
// If the original matrix is stored in a[][], matexp(n) calculates a^n.

#define DIM 10
#define MOD 1000000007
LL a[DIM][DIM],cpy[DIM][DIM];

void matmultiply(LL y[DIM][DIM])
{
    for(int i=0;i<DIM;i++)
        for(int j=0;j<DIM;j++)
        {
            cpy[i][j]=0;
            for(int r=0;r<DIM;r++)
                cpy[i][j]=(cpy[i][j] + a[i][r]*y[r][j]) % MOD;
        }
    memcpy(a,cpy,sizeof cpy);
}

void matexp(int n)
{
    if(n==1)
        return;
    else if(n%2==0)
    {
        matexp(n/2);
        matmultiply(a);
    }
    else
    {
        LL temp[DIM][DIM];
        memcpy(temp,a,sizeof a);
        matexp(n-1);
        matmultiply(temp);
    }
}

Saturday, September 14, 2013

Modular Multiplicative Inverse

Objective: To calculate modular multiplicative inverse of a number.(Refer to the link if you dont know what this term means)

Solution:
Two possible solutions are very nicely explained in the Wikipedia link. So, i will just share C++ implementations using both the methods

Using Extended Euclid:

void extended_gcd(int a, int b, int &gcd, int &x, int &y)
{
    x=0; y=1; gcd=b;
    int u=1,v=0,m,n,q,r;
    while(a!=0)
    {
        q=gcd/a; r=gcd%a;
        m=x-u*q; n=y-v*q;
        gcd=a; a=r; x=u; y=v; u=m; v=n;
    }
}

LL mod_inv(int a)
{
    int gcd,x,y;
    extended_gcd(a,MOD,gcd,x,y);
    if(gcd==1)
        return (LL)((x+MOD)%MOD);
}
Using Euler's Theorem:

Use modular exponentiation from here

Modular inverse is same as mod_exp(a,MOD-2,MOD).

Modular Exponentiation

Objective: To calculate (a^n)%MOD in O(logn) time, where a,n,MOD are constants.

Solution:
a^n = (a^(n/2) )^2 if n is even
           (a^(n-1))*a is n is odd
 Base cases:
a^1 = a
a^0 = 1

So we can solve this problem by recursion.

Code:

int mod_exp(int a, int n, int MOD) {
    if(n == 0)
        return 1%MOD;
    else if(n == 1)
        return a%MOD;
    else if(n&1)
       return (a*mod_exp(a,n-1,MOD))%MOD;
   else
   {
       int ret = mod_exp(a,n/2,MOD);
       return (ret*ret)%MOD;
   }
}
Note: To take care of overflow issues, it is recommended to use long long instead of int.

Iterative Version:

LL modexp(LL a, int n, LL MOD) {
    if(a == 0) {
        if(n == 0) return 1;
        else return 0;
    }
    LL ret = 1;
    while(n > 0) {
        if(n&1) {
            ret *= a;
            if(ret >= MOD) ret %= MOD;
        }
        n >>= 1;
        a *= a;
        if(a >= MOD) a %= MOD;
    }
    return ret;
}