避免算術溢出

假設有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

避免算術溢出

回答

相關問題