今日topcoderの問題を解いてて、浮動小数点の誤差ではまりました。問題を単純化したコードが以下になります。
#include ＜iostream＞ using namespace std; int main(int argc, char** argv) { double small = 1e-18; double big = 1; double added = small + big; cout ＜＜ added ＜＜ endl; // 1が出力される。(small分が切り捨てられてる) }
加算を行った結果、小数点以下の値が切り捨てられています。一瞬何が起こったのか解らなかったのですが、折角なので追ってみる事にしました。
まずdoubleの内部表現は次のようになります。(詳細はwikipediaを参照)
符号部(sign)が1bit、指数部(exponential)が11bit, 仮数部(significand)が52bitです。
実際に確認してみます。gdbで確認するには以下のようにします。(他に簡単な確認方法があれば教えて下さい。)
$ g++ -g test.cpp $ gdb ./a.out (gdb) x/g &small 0xbfffee88: 0x3c32725dd1d243ac (gdb) x/g &big 0xbfffee90: 0x3ff0000000000000 (gdb) x/g &added 0xbfffee98: 0x3ff0000000000000
見ての通り、0x3c32725dd1d243acと0x3ff0000000000000の加算結果が0x3ff0000000000000となっています。
まずbigの値を見てみると、符号部は0, 指数部は3ff, 仮数部は0です。これを先ほどの式に当てはめます。
上で見た式の通りにデータが構成されていますね！同様にsmallについても見てみましょう。
これで大分と事情が飲み込めますね。加算の際は指数部の桁をあわせる必要がありますが、smallとbigでは指数部に2^60倍の差があるため、smallの仮数部が60bit分右にシフトします。仮数部は全部で52bitしか無いので、結果的にすべて0になってしまい、smallの値は切り捨てられることになります。
このような現象は情報落ちと呼ばれていて、僕も学校で習った気はしますが、きちんと考えたのは今回が初めてでした。倍精度の浮動小数点といっても、絶対値の大きく違う数を同時に扱おうとすると簡単に誤差が発生してしまう事が解りました。まだ感覚は掴みきれていませんが、気をつけて行こうと思います。
関連する記事
タグ: algorithm
