[問題] long long int 的餘數運算

[DJWS (...)]

在網路上看到一段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 估計一個接近真正商的數出來
→ LPH66:所以 a*b - y*m 和真正的餘數不會差太多
→ LPH66:就可以直接取 % 了
推 LPH66:不過剛剛仔細看了一下  如果 a*b/m 太大 y 還是會溢位
→ LPH66:如傳 a = b = 4611686018427387904 (2^62) m = 1025 就爆了
→ LPH66:我會在 y 那行上面加 a %= m; b %= m; 這樣就應該沒事了
→ bleed1979:如果各自先mod m的話，計算y似乎不是很必要。
→ suhorng:各自先mod m的話, a*b有可能溢位, 之後計算(ab)%m結果會錯
→ suhorng:意思是 直接寫 a*b%m 即使各自先mod m仍然可能錯
→ bleed1979:取決於m多大吧？！
→ suhorng:m傳進來參數就是long long int了
→ suhorng:也是啦...
推 ke1vin:y 和 a*b 本來就是會溢位的
→ ke1vin:但他們仍然會是對的值 mod 2^63 (之類啦反正就正確值溢位)
→ ke1vin:重點是 r = (a*b-y*m) = a*b%m 不會超過 long long
→ ke1vin:所以總之就算溢位減回來的值會是對的
→ ke1vin:前提當然是溢位的實做確實是會乖乖再從 -2^63 往上加
→ DJWS:感謝各位！ 終於懂了 :D