fast modular multiplication methodI 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.
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%2 == 0)
long long int base1 = pow(fast_exp(base, exp/2),2);
if(base1 >= 1000000007)
long long int ans = (base* pow(fast_exp(base,(exp-1)/2),2));
if(ans >= 1000000007)
Yeah...we can't represent values greater than mod value in normal ways that's why we use mod value for checking the answers. ..