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?

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
– Richard Critten, Commented Jun 14, 2015 at 21:20
Technically speaking, everything after "it overflows" is undefined behavior when you're working with signed values; anything at all can happen, — user1084944
– user1084944, Commented Jun 14, 2015 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
– John Targaryen, Commented Jun 14, 2015 at 22:20

user1084944 · Accepted Answer · 2015-06-14 22:08:05Z

1

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.

answered Jun 14, 2015 at 22:08

user1084944

Sign up to request clarification or add additional context in comments.

Comments

Chris Dodd · Accepted Answer · 2015-06-14 23:59:21Z

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

Would one bit at a time mean an extra log(n) factor for multiplication?
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.

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

2 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Linked

Related