避免算术溢出

Question

假设您有两个大于2^32 (小于2^63)的正long值a和b，以及一个长整型c。在java和\或c中，执行以下操作的最佳方法是什么？

(a*b)%c

同时避免算术溢出。

编辑:C在2^34附近，有时a和b都在2^32和c之间……

对于我所处的特定情况，我最终避免了使用BigInteger。实际上，知道a和b的一个因子是可能的(并不总是这样)，所以我会利用modulo的算术属性。

Answer 1

假设一切都是肯定的，那么你可以使用下面的数学等式：

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

当然，这仍然不能消除溢出的可能性。

完全避免这个问题的最简单的方法是使用一个大整数库。

Answer 2

你可以比@Oli Charlesworth在他的(很好的)答案中建议的更进一步。您可以在因子a和b中进行分解(在所有的素因子中不是必需的，部分分解可能就足够了)，并在乘法的任何中间结果中执行模运算。虽然这可能比bignum的成本更高，因为它涉及相当多的部门，而且它们很昂贵。

Answer 3

在Java中，我会使用BigInteger

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