這個乘除法功能是否正確？

我試圖避免long long s和整數溢出在一些計算，所以我想出了以下函數來計算(a * b)/c（順序是重要的，因爲截斷整數除法）。這個乘除法功能是否正確？

unsigned muldiv(unsigned a, unsigned b, unsigned c) 
{ 
     return a * (b/c) + (a * (b % c))/c; 
}

是否有任何邊緣情況下，這不會按預期工作？

來源

2012-04-25 Electro

你不說*但如果它的速度我強烈懷疑任何額外DIV/MOD操作矮儲蓄。 – 2012-04-25 19:16:17

我假設你已經檢查過'c = 0'。 – twain249 2012-04-25 19:18:38

你沒有提到你是否希望輸出是一個整數或一個雙精度 - 因爲你正在進行除法。如果是您擔心的溢出問題，那麼您可以對'a'，'b'和'c'進行歸一化，然後（不）對結果進行歸一化。通過規範化，我的意思是分裂/乘以10的冪數。 – 2012-04-25 19:21:27

EDITED：對於原始顯而易見的邏輯正確的值的超集，這是正確的。它仍然沒有購買任何東西，如果c>b並可能在其他條件下。也許你對c的價值有所瞭解，但這可能無法達到預期的效果。 a,b,c的某些組合仍然會溢出。

編輯：假設你避免long long嚴格C++ 98的便攜性原因，您可以通過促進你的unsigned到double s表示碰巧有整數值做數學題獲得約52位精度。數學實際上可能比做三個積分更快。

來源

2012-04-25 19:19:37

如果'c> b'變成'（a * b）/ c'，因爲第一項退出並且'b％c' ='b'。此外，因爲這將是<'a'它不能溢出（因爲'a'適合）。 – twain249 2012-04-25 19:21:35

也許，但我不確定我是否可以用'double'可靠地計算出每一個可能的'（a * b）/ c'。 – Electro 2012-04-25 19:29:27

@Electro你不能，但取決於你的'b'，'b'，'c'的分佈，它可能比你原來的方法更多。如果你真的需要能夠處理每一個可能的輸入值，我強烈建議你只是咬緊牙關，用'long long'。 – 2012-04-25 19:49:21

這在很多情況下都失敗了。最明顯的是當a很大時，所以a * (b % c)溢出。在這種情況下，您可以嘗試交換a和b，但如果a,b和c都很大，則仍會失敗。考慮使用32位無符號的a = b = 2^25-1和c = 2^24。正確的結果是2^26-4，但a * (b % c)和b * (a % c)都會溢出。即使(a % c) * (b % c)也會溢出。

到目前爲止，解決這個問題的最簡單的方法是擴大乘法，以便獲得更高精度的中間產品。如果你沒有這些，你需要從較小的乘法和除法中綜合出來，這與實現你自己的biginteger庫非常相似。

如果你能機制保障是c是足夠的(c-1)*(c-1)不會溢出一個無符號的小，你可以使用：

unsigned muldiv(unsigned a, unsigned b, unsigned c) { 
    return (a/c)*(b/c)*c + (a%c)*(b/c) + (a/c)*(b%c) + (a%c)*(b%c)/c; 
}

這實際上給你「正確」的答案全部A和B - （ a * b）/ c％（UINT_MAX + 1）

來源

2012-04-25 22:14:05

爲了避免溢出，您必須先進行預分頻，然後乘以某個因子。

使用的最佳因子是c，只要a和b中的一個（或兩者）大於c。這就是Chris Dodd的功能。它具有（（a％c）*（b％c））的最大中間值，正如克里克所確定的，它小於或等於（（c-1）*（c-1））。

如果您可能出現a和b都小於c但（a * b）仍然可能溢出的情況（這可能是c接近字大小限制的情況），那麼最佳因子使用是兩個大的力量，將乘法轉化爲轉變。嘗試移動字大小的一半。

請注意，使用預先分割和後乘法相當於在沒有更長的單詞可用時使用更長的單詞。假設您不會丟棄低位，但只是將它們添加爲另一個名詞，那麼您只需使用幾個單詞而不是一個較大的單詞。

爲什麼*您避免`長long`我會讓你填寫的代碼英寸

來源

2012-05-04 15:15:36

這個乘除法功能是否正確？

回答

相關問題