2
//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?

user3664490
  • 217
  • 4
  • 13

2 Answers2

3

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.

p4plus2
  • 462
  • 4
  • 11
0

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.

Ivan Vergiliev
  • 3,771
  • 24
  • 23
  • so isn't i just need to chage to float or long int instead of int? – user3664490 May 27 '14 at 08:29
  • 1
    `long long` is still not large enough to fit 2^127. However, if you switch to floats or doubles, you won't be able to use `operator %` so you'd have to come up with a different implementation. (I think this is actually the reason `fmod` exists - because you can't use `%` instead.) – Ivan Vergiliev May 27 '14 at 08:32