Re: [問題] 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;
: }
: 請問為什麼這樣寫就不會溢位？
感謝各位板友幫忙
自己再嘗試回答一次
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)
推
02/15 17:56, , 1F
02/15 17:56, 1F
→
02/15 17:56, , 2F
02/15 17:56, 2F
推
02/15 19:38, , 3F
02/15 19:38, 3F
→
02/15 19:38, , 4F
02/15 19:38, 4F
→
02/15 19:39, , 5F
02/15 19:39, 5F
討論串 (同標題文章)