浮動小数点演算と誤差
たとえば平方数の判定なんかは二分探索させていたのですが、フォーラム見てると、かなり大きな数に対してもわりとみんな普通に浮動小数点数で計算してる模様。
floorSqrt n = bsearch 0 n where bsearch l u | m^2 > n = bsearch l (m-1) | (m+1)^2 > n = m | otherwise = bsearch (m+1) u where m = (l+u) `div` 2 floorSqrt' = floor . (+ eps) . sqrt . fromIntegral where eps = 1e-10
当然だけど後者の方が断然速いです。
TopCoderとかですっかり丸め誤差恐怖症になってしまった自分がいるのですが、丸め誤差が怖いのは蓄積するからなんですよね。だからこういう単発の使用はそれほど怖がらなくていいんじゃないか説。
特に sqrt や log みたいに、でかい数を小さくする系は誤差も小さそうだし、64bit整数くらいの範囲ならもっと浮動小数点演算を信頼してあげてもいいかなと思うようになりました。