私の友人 Christian が -1/2 を int にした場合には 0 か -1 かという話をしてくれた.Christian は binary search を書いていてこれが問題になったということである.lower bound で小さい方がみつからなかった場合にこれを -1 とした場合,
mid = (left+right)/2
left = -1, right = 0 の時, mid は C,C++,Java では 0 を, python, ruby では -1 となる.この簡単そうなコードが言語によって異なる結果というのは驚きだった.
これは丸めの方法による.C,C++,Java, elisp は 0 へのまるめ(truncation)を行うので,これは 0 である. python, ruby は floor をとるので -1 である.特に modulo 演算を考えると, python や ruby は
x = x/y + x%y
が成立するので有用である.modulo演算も負の数が入ってくると振舞いが言語に依存するので注意が必要である.
もう一つ,この mid を求めるコードは overflow の問題がある.そこで,
mid = low + (high - low)/2;
とすべきである.
参考文献
http://en.wikipedia.org/wiki/Modulo_operation
http://en.wikipedia.org/wiki/Rounding
http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
http://xlinux.nist.gov/dads//HTML/binarySearch.html
http://www.codecodex.com/wiki/Binary_search
謝辞
この話を教えてくださったChristian R.に感謝する.