CODEWITHSUNDEEP
c++cvisual-studio-2010modulo
WilHall
WilHall

Reputation: 11994

Modulo division returning negative number

I am carrying out the following modulo division operations from within a C program:

(5^6) mod 23 = 8

(5^15) mod 23 = 19

I am using the following function, for convenience:

int mod_func(int p, int g, int x) {
    return ((int)pow((double)g, (double)x)) % p;
}

But the result of the operations when calling the function is incorrect:

mod_func(23, 5, 6) //returns 8
mod_func(23, 5, 15) //returns -6

Does the modulo operator have some limit on the size of the operands?

Upvotes: 1

Views: 2985

Answers (4)

paddy
paddy

Reputation: 63471

5 to the power 15 is 30,517,578,125

The largest value you can store in an int is 2,147,483,647

You could use 64-bit integers, but beware you'll have precision issues when converting from double eventually.

From memory, there is a rule from number theory about the calculation you are doing that means you don't need to compute the full power expansion in order to determine the modulo result. But I could be wrong. Been too many years since I learned that stuff.

Ahh, here it is: Modular Exponentiation

Read that, and stop using double and pow =)

int mod_func(int p, int g, int x)
{
    int r = g;
    for( int i = 1; i < x; i++ ) {
        r = (r * g) % p;
    }
    return r;
}

Upvotes: 3

Daniel Fischer
Daniel Fischer

Reputation: 183888

As has been said, your first problem in

int mod_func(int p, int g, int x) {
    return ((int)pow((double)g, (double)x)) % p;
}

is that pow(g,x) often exceeds the int range, and then you have undefined behaviour converting that result to int, and whatever the resulting int is, there is no reason to believe it has anything to do with the desired modulus.

The next problem is that the result of pow(g,x) as a double may not be exact. Unless g is a power of 2, the mathematical result cannot be exactly represented as a double for large enough exponents even if it is in range, but it could also happen if the mathematical result is exactly representable (depends on the implementation of pow).

If you do number-theoretic computations - and computing the residue of a power modulo an integer is one - you should only use integer types.

For the case at hand, you can use exponentiation by repeated squaring, computing the residue of all intermediate results. If the modulus p is small enough that (p-1)*(p-1) never overflows,

int mod_func(int p, int g, int x) {
    int aux = 1;
    g %= p;
    while(x > 0) {
        if (x % 2 == 1) {
            aux = (aux * g) % p;
        }
        g = (g * g) % p;
        x /= 2;
    }
    return aux;
}

does it. If p can be larger, you need to use a wider type for the calculations.

Upvotes: 0

ouah
ouah

Reputation: 145839

The integral part of pow(5, 15) is not representable in an int (assuming the width of int is 32-bit). The conversion (from double to int in the cast expression) is undefined behavior in C and in C++.

To avoid undefined behavior, you should use fmod function to perform the floating point remainder operation.

Upvotes: 3

njkremer
njkremer

Reputation: 269

My guess is the problem is 5 ^ 15 = 30517578125 which is greater than INT_MAX (2147483647). You are currently casting it to an int, which is what's failing.

Upvotes: 1

Related Questions