避免算术溢出

假设有2个阳性long值a和b其是大于2^32（并且小于2^63），和一个长整数c。什么是最好的方式，在java和\或c，执行操作如避免算术溢出

(a*b)%c

，同时避免算术溢出。

编辑： c是围绕2^34，有时a和b只是2^32和c之间...

我使用BigInteger的具体情况我是在最后避免事实上，这是可能的。知道这两个a和b（并非总是如此）的一个约数，所以我会用的modulo算术性能，我的优势。

来源

2012-02-26 UmNyobe

假设'long'是一个64位的类型... – 2012-02-26 19:19:15

是做这个假设。 – UmNyobe 2012-02-26 19:23:29

'GCC 4.6'提供的类型'__int128'作为扩展：[*支持新的数据类型__int128用于具有足够宽的机器模式支持靶*]（http://gcc.gnu.org/gcc-4.6 /changes.html）。 – pmg 2012-02-26 19:33:31

假设一切的肯定，那么你可以使用下面的数学身份：

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

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

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

来源

2012-02-26 17:27:37

是的，这是我所拥有的。 c是大约2^34，有时a和b都只是2^32和c ... – UmNyobe 2012-02-26 17:32:01

值得指出的是，右侧是从溢流安全的，如果'C <= SQRT（LONG_MAX）'之间。 – 2012-02-26 17:32:23

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

来源

2012-02-26 17:40:46

http://bash.org/?946461 – 2012-02-26 17:49:11

我该如何评论评论？ – 2012-02-26 17:58:07

...'BigDecimal'，而不是'BigInteger'？ – 2012-02-26 18:33:38

你可以走得更远比@Oli查尔斯沃思表明他（好）的答案。您可以分解因子a和b（在所有素数因子中不必要，部分分解可能就足够了），并在乘法的任何中间结果中执行模数。虽然这可能比去参加昂贵的会更昂贵，因为它涉及不少部门，而且价格昂贵。

来源

2012-02-26 18:00:55 fortran

感谢。其实这就是我所做的。通常这种分解是昂贵的，但我意识到在我的情况下它不是（由于数字是如何产生的第一位）。 – UmNyobe 2012-02-26 19:34:49

据我所知，有没有办法解决你的问题，而更高的精度算术，以及至少LLVM的优化同意。

如果128位数学算法本身不可用，则需要使用通用的大整数库，或者从GnuCash中的较不常用的实现中获取所需的位，如Math128。

来源

2012-02-26 19:23:30 Christoph

避免算术溢出

回答

相关问题