//test.cpp
fmod( pow(2.0,127),467 );// Return result as 132 <-- correct answer
When i using my own implementation
int mod( int dividend , int divisor ){
return (dividend % divisor + divisor ) % divisor;
}
int a = mod ( pow(2.0,127),467 );// Wrong result , 441
//or direct use
int a = pow(2.0,127);
int b = a%467 // Will return wrong result , -21
i want to get answer 132, fmod does it, but why my implementation cannot get the correct answer?
The problem, as addressed by Ivan, is that you are exceeding the bounds of an integer. Unfortunately there is no native type which can hold 2^127 (Excluding using two 64 bit results as a synthetic 128 bit int).
However, fortunately for you, in this case you more likely what you want is powmod. Powmod is a pow function which computes mod at the same time as the power (as the name would suggest). Something like this should do the trick for you:
int powmod(int b, int e, int m)
{
int result = 1;
while(e > 0){
if(e & 1){
result *= b;
result %= m;
}
b *= b;
b %= m;
e >>= 1;
}
return result;
}
In this case, b is your base, e is your exponent, and m is your mod. So in this case powmod(2, 127, 467) returns 132 -- your intended answer. Hope this helps, and if you're dealing with a lot of big numbers and modular arithmetic I suggest you read an article or two on congruency of modular operations.
Edit: Fixed a grammar typo.
fmod takes double arguments, whereas your mod function takes ints. 2^127 does not fit into an int so it gets wrapped in some unexpected way.
