Tuesday, December 20, 2011

Calculating the multiplicative inverse

Given a number x, find its multiplicative inverse y for a given modulo N
i.e. (x*y) == 1(MOD N)

Where the multiplicative inverse is useful?

Lets assume we need to compute ((a1 * a2 *....)/(b1 * b2 * .....)) mod N
1 simple way is to compute the above expression as

long long res = 1;
for(int i = 0; i < n; i++)
    res *= a[i];
for (int i = 0; i < n; i++)
    res /= b[i];
res %= MOD;

But, wait there is a catch, what if a1* a2 * .... overflows the long long range or the datatype under use?

So what are the possible options. Some people might fall into the trap 

res = (res * a[i]) % MOD;
res = (res /a[i]) % MOD;

While first statement is perfectly correct, but the subsequent divisions operations are incorrect.
You can pick some of the examples to reason it out!

So moving ahead, one most common 'trick' which would hit us would be, how we used to perform these operations in our early school days.

Get the prime factorizations of a1, a2, a3...., b1, b2, b3, 
And then cancel out the common factors,
Then the problem reduces to find the multiplication of the left out factors(lets say c[]) which can be done by 

for(int i = 0; i < n; i++)
    res = (res * c[i]) % MOD;

But sooner or later you would realise, this easy looking task is actually quite expensive. Infact the good methods would take around O(sqrt(n)) per number to factorize itself.
So for (n + n) numbers with average value of x the overall complexity would be 

n * O(sqrt(x))

With this approach as the average value x increases the code would timeout for most of the cases.

So whats next? Most of us who are familiar with the set theory would be thinking about the possibility of computing the multiplicative inverse.
So formally, for a number x, a number y is a multiplicative inverse if 
(x * y) %  N = 1 or 
(x * y) == 1(MOD N)

A naive implementation to compute the inverse would be to try y for all the numbers between 1 to N - 1 and find the suitable match.

Well, there is a Fermat's Little theorem which could help us here, if MOD is prime number then the inverse can be given by

a^{m-2} \equiv a^{-1} \pmod{m}.

The a ^ n can be calculated in O(log n) time, for details you can refer here

So the overall complexity boils down to n * O(log M)

So what do we do if the MOD value is not a prime number? Can we solution this based on Fermat's theorem? This is left as an exercise to the reader :)

Sidenote, there are several other methods to achieve in a more optimised way.

No comments :

Post a Comment