二分探索でオーバーフロー
2006-06-09-2
[Programming][Algorithm]
二分探索(バイナリサーチ)の
404 Blog Not Found:(a+a)/2 == -a /* 半世紀もののバグ */
http://blog.livedoor.jp/dankogai/archives/50522708.html
とっくにぶち当たっていますよ。
suffix array のライブラリ SUFARY では対処済みです(前世紀)。
実装していた当時、GBサイズを扱う時にこれに悩まされて、結局両方を2で割ってから足すという回避策を採用しました。
見てみるとこんな感じ (sbr.* は long です)。
って、この overflow の話って結構メジャーなのでは?
なんかの本に書いてあったような記憶があるのだが思い出せない…。
気のせいかも。
元ネタ:
Official Google Research Blog: Extra, Extra - Read All About It:
Nearly All Binary Searches and Mergesorts are Broken
http://googleresearch.blogspot.com/2006/06/
extra-extra-read-all-about-it-nearly.html
関連:
- Cafe Babe - binarySearchメソッドのバグ
http://d.hatena.ne.jp/kazama/20060605/p2
- 古典的バイナリサーチアルゴリズムにバグ: ホットコーナーの舞台裏
http://iiyu.asablo.jp/blog/2006/06/05/393464
- Doblog - 日々礼賛 -
http://www.doblog.com/weblog/myblog/42113/2611927#2611927
- バグとintと古典的アルゴリズム
http://d.hatena.ne.jp/kappe1982/20060607#1149658236
int mid = (low + high) / 2;の計算でオーバーフローになる可能性。
404 Blog Not Found:(a+a)/2 == -a /* 半世紀もののバグ */
http://blog.livedoor.jp/dankogai/archives/50522708.html
確かにこれだけの大きさの配列をbsearchしたりsortしたりという状況はあまりなさそうですが、比較的身近な例ではsuffix arrayとかがこのケースにぶち当たりそうです。
とっくにぶち当たっていますよ。
suffix array のライブラリ SUFARY では対処済みです(前世紀)。
実装していた当時、GBサイズを扱う時にこれに悩まされて、結局両方を2で割ってから足すという回避策を採用しました。
見てみるとこんな感じ (sbr.* は long です)。
sbr.center = sbr.left / 2 + sbr.right / 2 + (1 & sbr.left & sbr.right);
って、この overflow の話って結構メジャーなのでは?
なんかの本に書いてあったような記憶があるのだが思い出せない…。
気のせいかも。
元ネタ:
Official Google Research Blog: Extra, Extra - Read All About It:
Nearly All Binary Searches and Mergesorts are Broken
http://googleresearch.blogspot.com/2006/06/
extra-extra-read-all-about-it-nearly.html
関連:
- Cafe Babe - binarySearchメソッドのバグ
http://d.hatena.ne.jp/kazama/20060605/p2
- 古典的バイナリサーチアルゴリズムにバグ: ホットコーナーの舞台裏
http://iiyu.asablo.jp/blog/2006/06/05/393464
- Doblog - 日々礼賛 -
http://www.doblog.com/weblog/myblog/42113/2611927#2611927
- バグとintと古典的アルゴリズム
http://d.hatena.ne.jp/kappe1982/20060607#1149658236