Vote Up 0 Vote Down

fast modular multiplication method

I was reading about Fast modulo multiplication.
Suppose we have a base b and an exponent e which may be very large.
Now we want to calculate Ans = b^e.
Now basically what we do is we select a large prime no. like (10^9 + 7) as given in below code snippet to ensure the calculations are kept within limit and hence faster result.
i.e
Mod = 10^9 + 7
Ans = b^e%Mod
But can somebody clarify that wouldn't yield unintended/wrong output as the actual output may be larger than is Modulus value.

long long int fast_exp(int base, int exp)
{
if(exp==1)
return base;
else
{
if(exp%2 == 0)
{
long long int base1 = pow(fast_exp(base, exp/2),2);
if(base1 >= 1000000007)
return base1%1000000007;
else
return base1;
}
else
{
long long int ans = (base* pow(fast_exp(base,(exp-1)/2),2));
if(ans >= 1000000007)
return ans%1000000007;
else
return ans;
}
}
}
flag

Answers


Vote Up 0 Vote Down
Yeah...we can't represent values greater than mod value in normal ways that's why we use mod value for checking the answers. ..
flag | link |
Vote Up 0 Vote Down
If a problem says give answer modulo 99, then in case your answer is coming to be 100, then you should output 1 for passing in the judge. ..
flag | link |

Your Answer

Login before answering

Login with facebook