double演算で保証される精度
自分の書いたdoubleを使ったプログラムが何桁保証されているのかわかんねぇ〜とか思ってただけで自分でちゃんと考えてみたことがなかったことに気づいたので自分で考えてみようと思う。間違ってたら教えてください。
doubleの基礎
doubleのbit配置
syyy yyyy yyyy xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx
- s : 符号 (1)
- y : 指数部 (11)
- x : 仮数部 (52)
精度が何桁かという話に関連してくるところは仮数部xなので、ここの話をする。
仮数部というのは、数値を2進数で
1.xxxx.... * 2^yyy
のように表した時の
xxxx....
を表す部分ということである。最上位が1なことは明らかなのでこの部分は表示されない。
値が0の時はどうするんだとか、詳しいことはWikipedia参照ってことで。
そういうことなのでdoubleの精度は
2^53 = 9007199254740992 = 9 * 10^15
あるということになる。だから精度は15,6桁あるとか言われるのだろう。
誤差の種類
まず、演算で発生する誤差の種類は
- 丸め誤差
- 情報落ち
- 桁落ち
- 打切り誤差
がある。
丸め誤差
小数部分を2^-54目で端数処理する(丸める)ことにより起こる
- 発生する演算:全て
- 誤差の大きさ:2^-54 * 指数部
- 演算後の精度:2進数で53桁
情報落ち
絶対値の大きい数と絶対値の小さい数を加減算したとき、絶対値の小さい数が無視されてしまう現象
- 発生する演算:加減算
- 誤差の大きさ:2^-54 * (大きい方の)指数部
- 演算後の精度:2進数で53桁
桁落ち
ほぼ等しい値を減算した時に丸め誤差が相対的に大きくなってしまうことで起こる
- 発生する演算:減算(正と負の加算)
- 誤差の大きさ:2^-54 * 演算前の指数部
- 演算後の精度:2進数で(53-演算前の指数部+演算後の指数部)桁
保証される精度
さて、こっからが本番のProgramで様々な演算を繰り返していった時に何桁までの精度が出るのかという話だが、結局のところプログラミングコンテストでも問題となるような大きな誤差が出るものは桁落ちと打切り誤差であることが分かる。ただ、桁落ちに付いてはどんな値の減算が起こるか見積もりにくいので一概に言うことができない。また、打切り誤差はどこで打ち切るかで誤差の値が変わるためそれぞれの関数の実装に付いてもっと調べないと何桁保証されるのかは分からない。
それに対して情報落ちに付いては計算が可能だ。
例えば正の実数の足し算をN回繰り返した場合は情報落ちしか起こらないので、最悪でも
2^-54 * N
の誤差しか出ない。
つまり、2進数で
54 - log2(N)
桁の精度は出ることになる。
だから今年のアジア大会のProblemCはNが300なので何も気にせずにdoubleで組んでも12,3桁は保証される。