[問題] 遇到超級長的資料要怎麼處理???

看板C_and_CPP作者 (呦厚厚)時間8年前 (2017/02/27 07:12), 編輯推噓7(7推 0噓 6→)
留言13則, 4人參與, 最新討論串1/1
我現在在做一個多維矩陣的行列式 用高斯消去法 因為 數值有小數 所以我會先把數值都乘到整數 並把數值的型態改成 long 因為在輾轉相除法時 明明是整數的double 還是常常會出現浮點數誤差 可能是因為誤差到overflow 所以就算我判斷他 只要 Math.abs < 0.00001 就跳出輾轉相除法 但還是會在輾轉相除法時跑無窮迴圈 我現在算這個 5x5 的矩陣行列式 11.00000 22.00000 33.00000 44.00000 55.00000 -33.00000 -55.00000 -33.00000 222.00000 444.00000 -99.00000 -777.00000 555.00000 33.00000 2345.00000 -0.00300 -444.00000 -0.77700 -0.88800 444.00000 444.00000 -333.00000 -0.00888 0.65400 0.02345 因為從小數補成整數 所以數值變很大 在計算過程中 超出了long的長度 如果是 double 應該是夠長 但是在輾轉相除法時 會跑不出迴圈 我應該用比 long 更大的型態去處理嗎??? 還是說有什麼更適當的方式解決??? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 68.206.227.13 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1488150754.A.7F6.html
推
02/27 07:18, , 1F
用 Bareiss algorithm？
02/27 07:18, 1F
推
02/27 11:38, , 2F
請問是高斯消去還是輾轉相除? 兩個解的問題不同
02/27 11:38, 2F
→
02/27 11:44, , 3F
抱歉沒看清楚是要算行列式 無腦的話可以先long long
02/27 11:44, 3F
→
02/27 11:45, , 4F
如果還是會超過的話 可以用GNU的GMP來做大數運算
02/27 11:45, 4F
推
02/27 12:03, , 5F
問題是在高斯消去法需要用除法 就算輸入是整數
02/27 12:03, 5F
→
02/27 12:04, , 6F
中間過程會變成分數
02/27 12:04, 6F
→
02/27 12:04, , 7F
如果不用大數實作有理數 就要用 Bareiss algorithm 了
02/27 12:04, 7F
→
02/27 12:05, , 8F
因為 Bareiss algorithm 保證中間過程都是整數
02/27 12:05, 8F
推
02/27 12:13, , 9F
看不懂 高斯消去為甚麼不能用小數????
02/27 12:13, 9F
推
02/27 12:57, , 10F
不是這樣就好了嗎 http://cpp.sh/25odo ??
02/27 12:57, 10F
推
02/27 13:36, , 11F
高斯消去法一般不能直接寫成程式, 會有數值穩定度問題
02/27 13:36, 11F
→
02/27 13:36, , 12F
一個小例子可見 #1EnRlkgw (Prob_Solve)
02/27 13:36, 12F
推
02/28 07:03, , 13F
謝謝樓上
02/28 07:03, 13F
‣ 更多 yhn0tgb60 的文章
文章代碼(AID): #1Ois3YVs (C_and_CPP)