二分探索について、chokudai氏とbeepcap氏との議論をまとめてみた

chokudai(高橋 直大)@AtCoder社長 @chokudai

@beepcap （さっきの続き）言えたんですけど、主張が結構あやふやだったので、何が言いたいのか全く分からずじまいでした＞＜ 今回は半分半分で決めていく二分探索でしたけど、上位nbitを決めていくような二分探索は絶対定数なので、定数ループがダメ、ってことはないかと・・・

beepcap @beepcap

@chokudai 固定小数点数ならそもそも切り捨てだから振動しませんし、固定回数のループはループを抜けてきた時に振動が発生しているのか、それともループ回数が不足していたのかを別途判定する(しかも、最悪またループしなきゃ！)すひつようがある時点でナンセンスです。

chokudai(高橋 直大)@AtCoder社長 @chokudai

@beepcap 振動しない代わりにオーバーフローするからこの場合ダメですよね？（そもそも精度が足りないのが問題、って話です） 固定回数のループは、「差をこれだけ縮めたい」っていうのを明確に記述する上で最も有効です。（今回は/2の処理を100回できる、というのが明確になる）

beepcap @beepcap

@chokudai 後半の意味はさっぱりわかりません。前半は目的のない関数なので、何がダメなのかはわかりませんが、もしもオーバーフローを気にするのであれば、多倍長の演算が行えるライブラリを利用すべきです。

beepcap @beepcap

@chokudai かりに、後半の話で100回行ったから、それがなんなのでしょうか？

chokudai(高橋 直大)@AtCoder社長 @chokudai

@beepcap 理解できないなら説明しないでいいやって感じになったからいいです・・・（二分探索で達成したいことをわかっている人向けの話でした）＿

chokudai(高橋 直大)@AtCoder社長 @chokudai

64bit浮動小数点数でできて64bit固定小数点数で処理できない課題が与えられたときに、後者を推奨するのはマジで判らないのでそこはもういいや・・・。

chokudai(高橋 直大)@AtCoder社長 @chokudai

たぶん64bitじゃなくて多倍長なんだろうけど・・・。多倍長いらないのに多倍長使うことないやん・・・

chokudai(高橋 直大)@AtCoder社長 @chokudai

別にループ回数を十分な定数回にしなくても、正確に書けるなら良い。（ただそれを百発百中正確に書ける人は、自分よりもはるかにアルゴリズムを正確に記述する能力がある人である）

beepcap @beepcap

実数の二分探索になんで深度がだいじなんだろう？

beepcap @beepcap

何回目で振動が始まるかはとても大事な要素だけど、振動した結果を含めたものが100回に達したという情報はなんのやくに立つんだ？

beepcap @beepcap

なんだろう、100って決め打ちにすると、探索が終わらないうちに処理が終わる危険性が無いかって話が、なんでこじれるのだろう。