CODEWITHSUNDEEP
javacmathprecision
UmNyobe
UmNyobe

Reputation: 22890

Avoiding arithmetic overflow

Assume you have 2 positive long values a and b which are greater than 2^32 (and smaller than 2^63), and an long integer c. What is the best way, in java and\or c, to perform operations such as

(a*b)%c

while avoiding arithmetic overflow.

Edit : c is around 2^34, and sometimes both a and b are just between 2^32 and c...

I finally avoided using BigInteger for the specific situation I was in. Indeed, It was possible to know one divisor of both a and b (not always the case), so I would use the arithmetic properties of modulo to my advantage.

Upvotes: 2

Views: 374

Answers (4)

Christoph
Christoph

Reputation: 169563

To the best of my knowledge, there's no way to solve your problem without higher precision arithmetics, and at least LLVM's optimizer agrees.

If 128-bit math is not available natively, you'll need to use a general-purpose big integer library, or take the bits you need from a less general implementation like Math128 from GnuCash.

Upvotes: 1

Oleg Mikheev
Oleg Mikheev

Reputation: 17444

In Java I would use BigInteger:

BigInteger bd = BigInteger.valueOf(2).pow(33);
System.out.println(bd.multiply(bd).remainder(BigInteger.valueOf(2).pow(34).add(BigInteger.valueOf(1))));

Upvotes: 1

fortran
fortran

Reputation: 76057

You can go even further than what @Oli Charlesworth suggests in his (good) answer. You can decompose in factors a and b (not necessary in all the prime factors, a partial decomposition might be enough) and perform the modulus in any intermediate result of the multiplication. Although this is likely to be more costly than going for the bignum, as it will involve quite a few divisions and they are expensive.

Upvotes: 2

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272487

Assuming everything's positive, then you can use the following mathematical identity:

(a*b)%c == ((a%c) * (b%c)) % c

Of course, this still doesn't eliminate the possibility of overflow.

The easiest way to completely avoid the issue is to use a big-integer library.

Upvotes: 8

Related Questions