How does int(or long long) overflow in c++ affect modulus?

Question

Suppose I have two long longs, a and b, that I need to multiply, then get the value mod k for some large k, such that a, b, and k are all in the range of long long but not of int. For simplicity, a, b < k.

Thus the code would be:

long long a, b, k;
cin >> a >> b >> k;
cout << (a * b)%k << "\n";

However, since a and b are so large, if you multiply like above, and it overflows and becomes negative, then mod k would be a negative number and incorrect.

How can you ensure that the value mod k is correct?

Edit: As a bonus, how does this work in Java? Is it the same, as expected? Or is BigInteger needed?

See http://stackoverflow.com/questions/4240748/allowing-signed-integer-overflows-in-c-c — juanchopanza, Jun 14 '15 at 20:54
Try using the fact that (a * b) % k == ((a % k) * (b % k)) % k . If k is smaller than long this will work. If not you will need to do some simple multiple-precision. — Richard Critten, Jun 14 '15 at 21:20
Technically speaking, everything after "it overflows" is *undefined behavior* when you're working with signed values; anything at all can happen, — , Jun 14 '15 at 22:04
@RichardCritten, please read the question and comments before you answer. nneonneo already pointed out that a,b < k in the comment _right above_ yours, and my second sentence in the question says a, b < k. Thus your method is no better than my method, as has been pointed out before. — John Targaryen, Jun 14 '15 at 22:20

Chris Dodd · Answer 1 · 2015-06-14T23:59:21.337

1

If you know the values are less than ULONGLONG_MAX/2 (so an add won't overflow), you can do the multiply one bit at a time:

unsigned long long mulmod(unsigned long long a, unsigned long unsigned long b, long long m) {
    unsigned long long rv = 0;
    a %= m;
    b %= m;
    while (b) {
        if (b&1) { rv += a; if (rv >= m) rv -= m; }
        a += a; if (a >= m) a -= m;
        b >>= 1; }
    return rv; }

If you know you're running on gcc/x86_64, you could try:

unsigned long mulmod(unsigned long a, unsigned long b, unsigned long m) {
    unsigned long rv;
    asm ("mulq %2; divq %3" : "=d"(rv), "+a"(a): "S"(b), "c"(m));
    return rv;
}

which will work up to ULONG_MAX

If your numbers get bigger than that, you'll need to go to a multiprecision library such as GMP

edited Jun 14 '15 at 23:59

answered Jun 14 '15 at 22:01

Chris Dodd

119,907
13
134
226

Would one bit at a time mean an extra log(n) factor for multiplication? – John Targaryen Jun 14 '15 at 22:18
2

Since the maximum size possible here is 63 or 127 bits (depending on the size of long long on your machine), asymtotic perforcemance doesn't really apply. – Chris Dodd Jun 14 '15 at 23:42

score 1 · Accepted Answer · answered Jun 14 '15 at 22:08

Many compilers offer a 128-bit integral type. For example, with g++ you can make a function

static inline int64_t mulmod(int64_t x, int64_t y, int64_t m)
{
    return ( (__int128_t)x * y) % m;
}

Aside: if you can, try to stick to unsigned integer types when you're doing modular arithmetic. The rounding behavior of integer division makes using % very awkward when signed values are involved.

How does int(or long long) overflow in c++ affect modulus?

2 Answers2