pya! ボク、さかな！（悲
http://pya.cc/pyaimg/pimg.php?imgid=1504

ボクさかな、
きのう海、
きょうはかまぼこ。

もの悲しい…。

■小林健一郎 / カーニハン&リッチー『プログラミング言語C』を読む

Programming Pearls （珠玉のプログラミング）を翻訳した小林健一郎さんは最近こんな本を出しています。
あのK&Rを読む、という本みたい。これは気になりすぎ。
今月は無理だけど、落ち着いたら読んでみる予定。

二分探索(バイナリサーチ)の

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

珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造 posted with Yasazon on 2006.06.09 [copy] ジョン ベントリー, Jon Bentley, 小林 健一郎 定価：￥ 3,570 発売日：2000/10 出版社/メーカー：ピアソンエデュケーション おすすめ度： (9 reviews) 納得！アルゴリズムは重要 プログラマなら読むべき本 アルゴリズムって何? 視点が変わる本です 自信をなくしそう…

ref. [2004-02-05-1][2005-08-11-1]

一昨日、13人で本格インドカレーランチ。
六本木一丁目方面まで遠征。ぞろぞろと。
おいしいです。いつもとはちょっと違う味付けで新鮮。
ちょっとオフィスからは遠いけど、散歩がてらときどき訪れたいと思います。



インド料理 六本木 Devi Fusion（デヴィ・フュージョン）
http://devi-group.com/devifusion/
http://r.tabelog.com/tokyo/A1307/A130701/13015383/
場所：東京都港区六本木3-3-15 SKビル

by ALPSLAB slide

店内の様子。2Fもあります。螺旋階段の上。今回は行かず。



カレーの様子。



飲み物つきます。


追記090330:
久しぶりにランチに行ったので写真を載せておきます。
ランチはリーズナブルな上、ボリューム、バリエーション、おいしさ、すべてが高水準です！