トップ «前の日記(2013-04-08) 最新 次の日記(2013-04-14)» 編集

Route 477



2013-04-09

[ruby] Ruby 2.0のRange#bsearchが無限区間の二分探索に対応している件

range.cのrdoc見てたら衝撃のサンプルコードが…

(0.0...Float::INFINITY).bsearch {|x| Math.log(x) >= 0 } #=> 1.0

0からFloat::INFINITYまでの間を二分探索する…だと?

実際にirbで試してみた。

irb(main):003:0> (0.0...Float::INFINITY).bsearch {|x|p x;  Math.log(x) >= 0 }
1.4999999999999998
1.305209627960036e-154
1.403377390202847e-77
4.59177480789956e-39
8.300922883092142e-20
3.528839442878961e-10
2.3007392883300778e-05
0.005874633789062499
(中略)
0.9999999999999982
0.9999999999999991
0.9999999999999996
0.9999999999999998
0.9999999999999999
=> 1.0

ちゃんと動きました。無限を無限のまま扱っている。凄い。ヤバイ。

実装上は、Floatを64bit整数にマッピングすることで実現しているらしい。