浮動小数点数が絡む実装のエラーパターンと対策法を紹介します
バックオフィスチームの棟朝です。普段はバックオフィスチームに在籍していますが、趣味で競技プログラミングに取り組んでいます。競技プログラミングでは計算量の改善やグラフの探索などアルゴリズムの問題のほか浮動小数点数を考慮したプログラミングの問題も出題されます。今回はそのなかで身につけた浮動小数点数の実装のよくあるミスと対策を紹介します。
環境
Python 3.7.12
PyPy 7.3.6
変換
Pythonのfloatなど多くの言語では小数は精度で16桁しか持てないです。
(2 進 53 桁) ≃ (10 進 16 桁
>>>> 1/3 0.3333333333333333 // 精度16
整数→小数
Pythonの整数は多倍長整数なので制限がないので、整数の方が桁数を多く持てます。
Goなどint64型が整数の場合でも、整数は18桁(2 進 64 桁) ≃ (10 進 18 桁)まで持てるので、小数の最大桁数 < 整数の最大桁数です。なので、大きい整数から小数に変換すると誤差が生じます。
>>>> a = 10**18-42 >>>> a 999999999999999958 // 18桁 >>>> float(a) 1e+18 // 999999999999999999 ≠ 10**18-42 小数に変換して丸め込まれてる
tips: 大きい値は小数で持ってはいけない
小数→整数
切り捨てられますが、整数の方が保持できる桁数が大きいので誤差はないです。
>>>> int(3.14) 3
例外として、四捨五入で誤差出る場合があります。 例えば、Pythonだとround関数の偶数丸めを採用しており、入力に最も近い偶数を選択するという仕様になっています。
>>>> round(0.5) 0 >>>> round(1.5) 2
回避策として２つあります。
より大きい精度の小数(EPS: 許容誤差)を加算して、四捨五入すると期待通りの結果になります。
>>>> round(0.5+0.05) 1
文字列で持って、小数部分の値を確認してもokです
s = str("0.5") if 4 < int(s[2]): print(int(float(s))+1 ) // 1 else: print(int(float(s)))
tips: 四捨五入は利用する関数の仕様を調べる
演算
小数が絡む乗算は基本NGです。普通に低い精度でもミスります。計算結果を２進数で表現できないため近似値が利用されるからです。
乗算
>>>> a = 251 >>>> b = 0.01 >>>> a*b 2.5100000000000002
演算は整数で計算しましょう
>>>> a = 251 >>>> b = 0.01 >>>> b *= 100 // bを整数に直す 1.0 >>>> ans = a*b // 小数を介さずa*bしましょう 251.0 >>>> ans //= 100 // 100で割って戻す 2.51
tips: 小数の演算は整数で行おう
除算
除算は多くの言語で切り捨て除算になります。
>>> 201/10 // 徐算 20.1 >>>> 201//10 // 切り捨て徐算 20
注意が必要なのは、負数の除算です。
結論から言うと言語によって結果が異なります。
>>>> -201/10 -21
Go
package main import "fmt" func main() { fmt.Println(-201 / 10) // -20 }
-201÷10=-20.1でこれを切り捨てると[-20.1] = -21ですが(Python)、Goでは結果が異なります。
Goにおける除算は「小数部分を無視した数学的な商」を計算しているからです。-201÷10=-20.1で0.1を無視して-20です。
tips: 負数の除算は言語仕様を確認しよう
参考
https://atcoder.jp/contests/abc226/tasks/abc226_a
https://atcoder.jp/contests/abc239/editorial/3390
