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

看板C_and_CPP作者 (...)時間14年前 (2012/02/14 21:37), 編輯推噓3(3推 0噓 15→)
留言18則, 5人參與, 最新討論串1/4 (看更多)
在網路上看到一段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)
推
02/14 21:50, , 1F
y 是估計商 用 double 估計一個接近真正商的數出來
02/14 21:50, 1F
→
02/14 21:50, , 2F
所以 a*b - y*m 和真正的餘數不會差太多
02/14 21:50, 2F
→
02/14 21:51, , 3F
就可以直接取 % 了
02/14 21:51, 3F
推
02/14 22:03, , 4F
不過剛剛仔細看了一下 如果 a*b/m 太大 y 還是會溢位
02/14 22:03, 4F
→
02/14 22:03, , 5F
如傳 a = b = 4611686018427387904 (2^62) m = 1025 就爆了
02/14 22:03, 5F
→
02/14 22:06, , 6F
我會在 y 那行上面加 a %= m; b %= m; 這樣就應該沒事了
02/14 22:06, 6F
→
02/14 22:11, , 7F
如果各自先mod m的話，計算y似乎不是很必要。
02/14 22:11, 7F
→
02/14 22:15, , 8F
各自先mod m的話, a*b有可能溢位, 之後計算(ab)%m結果會錯
02/14 22:15, 8F
→
02/14 22:15, , 9F
意思是 直接寫 a*b%m 即使各自先mod m仍然可能錯
02/14 22:15, 9F
→
02/14 22:18, , 10F
取決於m多大吧？！
02/14 22:18, 10F
→
02/14 22:20, , 11F
m傳進來參數就是long long int了
02/14 22:20, 11F
→
02/14 22:20, , 12F
也是啦...
02/14 22:20, 12F
推
02/14 22:28, , 13F
y 和 a*b 本來就是會溢位的
02/14 22:28, 13F
→
02/14 22:29, , 14F
但他們仍然會是對的值 mod 2^63 (之類啦反正就正確值溢位)
02/14 22:29, 14F
→
02/14 22:30, , 15F
重點是 r = (a*b-y*m) = a*b%m 不會超過 long long
02/14 22:30, 15F
→
02/14 22:30, , 16F
所以總之就算溢位減回來的值會是對的
02/14 22:30, 16F
→
02/14 22:31, , 17F
前提當然是溢位的實做確實是會乖乖再從 -2^63 往上加
02/14 22:31, 17F
→
02/14 23:09, , 18F
感謝各位！ 終於懂了 :D
02/14 23:09, 18F
‣ 更多 DJWS 的文章
文章代碼(AID): #1FEcEezR (C_and_CPP)
‣ 更多 DJWS 的文章
文章代碼(AID): #1FEcEezR (C_and_CPP)