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

[DJWS (...)]

※ 引述《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;
: }
: 請問為什麼這樣寫就不會溢位？

感謝各位板友幫忙
自己再嘗試回答一次

a*b 與 y*m 其實都會溢位
但是我們知道正確的r一定小於m，一定放得進64bit
所以事實上 a*b 與 y*m 有差別的地方就只有低位數的64bit
而高位數一定是完全相同

正確的 a*b 與 y*m，高位數相減後就會完全消失
因此正確的 a*b-y*m 可以當作是低位數64bit相減

溢位的 a*b 與 y*m，高位數完全消失
因此溢位的 a*b-y*m 其實也是低位數64bit相減
前後一致，可知減法的結果是正確的

另外
m很小的時候  y會溢位  y*m就會算錯
所以一開始就要先做 a %= m; b %= m;
確保y不會溢位

// r = a * b % m
long long int mulmod(long long int a, long long int b, long long int m) {
    a %= m; b %= 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 23:24)
※ 編輯: DJWS            來自: 61.230.128.220       (02/14 23:24)
推 tropical72:分析一下ieee754,64bits,mantissa=52+1bits,故double
→ tropical72:不會有誤差情況下,max/min= +- 2^52 -1
推 LPH66:嗯  所以 y 只有高位52位左右是對的  但在 a,b<y 時足夠了
→ LPH66:剩下的就交給 a*b-y*m 來補足
→ LPH66:                                      ↑a,b<m  打錯了..