[Python] 数値誤差恐るべし。。。 -AtCoder学習日記 #3
概要
今回はABC215-Bについてです。
コード自体は簡単なのですが「誤差」でWAになってしまいました。
ACできないコード
import math n = int(input()) print(math.floor(math.log2(n)))
ほとんどACなのですが一部だけWAになってしまっています。
なぜ誤差が出るのか
そもそも誤差はなんで生まれるのかについてです。
整数を扱っている際には特に誤差は生じないのですが、問題は小数を扱っている時です。
通常コンピュータでは10進数を2進数に変換して計算します。
そのため2進数にすると循環小数になってしまうような10進数を扱うと、循環している部分が丸められてしまうため正確な値にならないのです。
誤差を起こさないための対策
10進数同士の和差積商であれば、pythonのdecimalモジュールとfractionsモジュールを用いることで解決できるようです。参考文献のサイトに例が載っているのでそちらを参照してみてください。しかし、
floatの計算→Decimalの計算→Fractionの計算、の順番に計算速度が遅くなります。
とのことですので、競プロにはあまり向かない気がします。
解説にもあるように
競技プログラミングにおいて、整数性のある問題に対して整数性を外して実数で処理することには危険が伴います。整数性のある問題はなるだけ整数型で処理することをおすすめしますが、どうしても実数型が必要な際は注意して取り扱いましょう。
を忠実に守るのが良さそうです。。。
ACできたコード
import numpy n = int(input()) n = numpy.array(n).astype('float128') s = numpy.log2(n) print(s.astype('int64'))
Numpyの型変換で4倍精度浮動小数点型(float128)を用いることでACになりました。
まとめ
- 小数の計算するときには誤差に気をつける。
- decimal, fractionsモジュールを使うことで誤差をなくせる
- そもそも整数を扱う問題を実数に落とし込むのは危険
