二分探索について、chokudai氏とbeepcap氏との議論をまとめてみた
@beepcap (さっきの続き)言えたんですけど、主張が結構あやふやだったので、何が言いたいのか全く分からずじまいでした>< 今回は半分半分で決めていく二分探索でしたけど、上位nbitを決めていくような二分探索は絶対定数なので、定数ループがダメ、ってことはないかと・・・
2016-05-09 21:12:32寄り道
@chokudai 固定小数点数ならそもそも切り捨てだから振動しませんし、固定回数のループはループを抜けてきた時に振動が発生しているのか、それともループ回数が不足していたのかを別途判定する(しかも、最悪またループしなきゃ!)すひつようがある時点でナンセンスです。
2016-05-09 19:51:10@beepcap 振動しない代わりにオーバーフローするからこの場合ダメですよね?(そもそも精度が足りないのが問題、って話です) 固定回数のループは、「差をこれだけ縮めたい」っていうのを明確に記述する上で最も有効です。(今回は/2の処理を100回できる、というのが明確になる)
2016-05-09 19:53:46@chokudai 後半の意味はさっぱりわかりません。前半は目的のない関数なので、何がダメなのかはわかりませんが、もしもオーバーフローを気にするのであれば、多倍長の演算が行えるライブラリを利用すべきです。
2016-05-09 19:56:38@beepcap 理解できないなら説明しないでいいやって感じになったからいいです・・・(二分探索で達成したいことをわかっている人向けの話でした)_
2016-05-09 19:57:52その後
64bit浮動小数点数でできて64bit固定小数点数で処理できない課題が与えられたときに、後者を推奨するのはマジで判らないのでそこはもういいや・・・。
2016-05-09 21:14:37たぶん64bitじゃなくて多倍長なんだろうけど・・・。多倍長いらないのに多倍長使うことないやん・・・
2016-05-09 21:14:53別にループ回数を十分な定数回にしなくても、正確に書けるなら良い。(ただそれを百発百中正確に書ける人は、自分よりもはるかにアルゴリズムを正確に記述する能力がある人である)
2016-05-09 21:23:18