作者DJWS (...)
看板C_and_CPP
標題[問題] long long int 的餘數運算
時間Tue Feb 14 21:37:39 2012
在網路上看到一段code
// r = a * b % m
long long int mulmod(long long int a, long long int b, long long int m) {
long long int y = (long long int)((double)a*(double)b/m+0.5);
long long int r = (a*b-y*m) % m;
if (r < 0) r += m;
return r;
}
請問為什麼這樣寫就不會溢位?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.128.220
※ 編輯: DJWS 來自: 61.230.128.220 (02/14 21:39)
推 LPH66:y 是估計商 用 double 估計一個接近真正商的數出來 02/14 21:50
→ LPH66:所以 a*b - y*m 和真正的餘數不會差太多 02/14 21:50
→ LPH66:就可以直接取 % 了 02/14 21:51
推 LPH66:不過剛剛仔細看了一下 如果 a*b/m 太大 y 還是會溢位 02/14 22:03
→ LPH66:如傳 a = b = 4611686018427387904 (2^62) m = 1025 就爆了 02/14 22:03
→ LPH66:我會在 y 那行上面加 a %= m; b %= m; 這樣就應該沒事了 02/14 22:06
→ bleed1979:如果各自先mod m的話,計算y似乎不是很必要。 02/14 22:11
→ suhorng:各自先mod m的話, a*b有可能溢位, 之後計算(ab)%m結果會錯 02/14 22:15
→ suhorng:意思是 直接寫 a*b%m 即使各自先mod m仍然可能錯 02/14 22:15
→ bleed1979:取決於m多大吧?! 02/14 22:18
→ suhorng:m傳進來參數就是long long int了 02/14 22:20
→ suhorng:也是啦... 02/14 22:20
推 ke1vin:y 和 a*b 本來就是會溢位的 02/14 22:28
→ ke1vin:但他們仍然會是對的值 mod 2^63 (之類啦反正就正確值溢位) 02/14 22:29
→ ke1vin:重點是 r = (a*b-y*m) = a*b%m 不會超過 long long 02/14 22:30
→ ke1vin:所以總之就算溢位減回來的值會是對的 02/14 22:30
→ ke1vin:前提當然是溢位的實做確實是會乖乖再從 -2^63 往上加 02/14 22:31
→ DJWS:感謝各位! 終於懂了 :D 02/14 23:09