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

看板C_and_CPP作者LPH66 (-858993460)時間14年前 (2012/02/15 23:16)推噓8(8推 0噓 7→)

留言15則, 7人參與討論串4/4 (看更多)

※ 引述《tropical72 (藍影)》之銘言： : ※ 引述《DJWS (...)》之銘言： : : 感謝各位板友幫忙 : : 自己再嘗試回答一次 : : a*b 與 y*m 其實都會溢位 : : 但是我們知道正確的r一定小於m，一定放得進64bit : 重點是在算 y 的時候就有捨位誤差了，到後面會與正確結果愈差愈遠， : 這結果是你所能接受的？ : < 以下恕刪 >。這樣一提我才發現果然這樣子還是會出事... 剛剛試了一下傳 a = b = 4611686018427387902 (2^62 - 2) m = 4611686018427387903 (2^62 - 1) 進去理論上因為 a = b = m-1 所以 a*b mod m = 1 但實際跑程式的結果卻是 5 裡面的計算是這樣子的: 如上文由於 double 的精確度關係 y 這商只有高位 53 bit 是正確的於是當再乘上一個很大的 m 時 y*m 有效的那 53 bit 就完全不在低 64 bit 的範圍了如此一來 a*b - y*m 的值會混入了不準確但也溢出 64-bit 的位數就不再正確了以此例來說 y 應該要是 m-2 (2^62-3) 但是因為只精準到高 53 bit 於是"算"出來的 y 值是 2^62 因此 y*m 的"值" 2^124 - 2^62 只有那 2^124 可信 -2^62 不在有效數字範圍裡但偏偏因為溢位的關係丟掉的是 2^124 所以 a*b - y*m 的答案混入了 2^70 ~ 2^65 這些不準確的 bit 因此就不正確了由此看來 m^2 < 2^(64+53) => m < 2^58.5 ≒ 4.076*10^17 應該是保證安全的大小這樣即使 y 有誤差但 a*b 和 y*m 溢出去的部份保證是一樣的因此相減可以抵消 a*b - y*m 的值才保證是正確的捨去誤差的部份只要全部都有被 a*b - y*m 掌握住那就沒什麼問題 -- 其實我上面故意略過一個問題沒說那就是 y 還是可能溢位!! 問題發生在當 y 接近 2^63 時因為精確度只有 53 bit 的關係它會被近似成 2^63 問題是有號 64-bit 整數是放不下 2^63 的因此由浮點數轉回整數時它會被轉成 -2^63 這正是溢位那麼 y 溢位的後果也就可想而知了... -- 'Oh, Harry, don't you see?' Hermione breathed. 'If she could have done one thing to make absolutely sure that every single person in this school will read your interview, it was banning it!' ---'Harry Potter and the order of the phoenix', P513 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.230.62

推

ericinttu

02/15 23:23, , 1^F

02/15 23:23, 1^F

推

loveme00835

02/16 01:05, , 2^F

02/16 01:05, 2^F

推

tropical72

02/16 14:22, , 3^F

02/16 14:22, 3^F