Avoiding arithmetic overflow

Question

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.

gcc 4.6 provides the type __int128 as an extension: Support for a new data type __int128 for targets having wide enough machine-mode support.. — pmg
– pmg, Commented Feb 26, 2012 at 19:33
if c is exactly 2^34 or any power of 2, the result will be the same whether you have an overflow or not. — Peter Lawrey
– Peter Lawrey, Commented Feb 26, 2012 at 20:59

Oliver Charlesworth · Accepted Answer · 2012-02-26 17:27:37Z

8

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.

answered Feb 26, 2012 at 17:27

Oliver Charlesworth

274k34 gold badges591 silver badges687 bronze badges

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

2 Comments

UmNyobe Over a year ago

yes this is what I have. c is around 2^34, and sometimes both a and b are just between 2^32 and c...

Ted Hopp Over a year ago

It's worth pointing out that the right side is safe from overflow if c <= sqrt(LONG_MAX).

fortran · Accepted Answer · 2012-02-26 18:00:55Z

2

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.

answered Feb 26, 2012 at 18:00

fortran

76.6k27 gold badges143 silver badges180 bronze badges

1 Comment

UmNyobe Over a year ago

Thanks. Actually that's what I did. Usually this decomposition is costly, but I realized that In my case It was not (due to how the numbers were generated in the first place).

Oleg Mikheev · Accepted Answer · 2012-02-26 18:41:38Z

1

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))));

edited Feb 26, 2012 at 18:41

answered Feb 26, 2012 at 17:40

Oleg Mikheev

17.5k16 gold badges77 silver badges98 bronze badges

1 Comment

Louis Wasserman Over a year ago

...BigDecimal, and not BigInteger?

Christoph · Accepted Answer · 2012-02-26 19:23:30Z

1

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.

answered Feb 26, 2012 at 19:23

Christoph

171k36 gold badges188 silver badges243 bronze badges

Collectives™ on Stack Overflow

Avoiding arithmetic overflow

4 Answers 4

2 Comments

1 Comment

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

1 Comment

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related