タイトル詐欺じゃないですか？新鮮なぽかいこをお届け

ぽか

誤差です（誤差なので）

今週の ABC は私の担当じゃなかったので見ていなかったんですけど（ふまじめぽかいこ）、誤差トピックが出ているらしいと話を聞いて飛び起きて問題を解きました

$\dfrac1D\sum x _ i ^ 2-\left(\dfrac1D\sum x _ i\right) ^ 2$ をそのまま計算すると困って、$D ^ 2$ 倍した整数を求めてから $D ^ 2$ で割ると困らない話をします。特に、割り算のあたりから double とか long double で計算していると思って話をします。

みなさんももう浮動小数点数の演算と誤差に慣れてきたので困る・困らない理由は説明できちゃいますか？そうかも

そのまま計算すると困るのはどうして

$\dfrac1D\sum x _ i ^ 2$ には少なくとも $\dfrac12\operatorname{ulp}$ くらい相当の相対誤差が乗っています（正規化数が動く範囲を超えることはないですが、ちょうどの値は表せないかもしれないので）。 double だと $10 ^ {-15}$ くらい、long double だと $10 ^ {-18}$ くらいだと思います。 $\dfrac1D\sum x _ i ^ 2$ の最大値は小さく見積もっても $10 ^ {16}$ くらいの値になるので、最悪ケースでは $10$ とか $10 ^ {-2}$ くらいの絶対誤差が生じうることになります。

$\left(\dfrac1D\sum x _ i\right) ^ 2$ についても同様です。

すると、求める答え $\dfrac1D\sum x _ i ^ 2-\left(\dfrac1D\sum x _ i\right) ^ 2$ のスケールがある程度小さいとうまくいかない気がしてきますね。実際、$10 ^ {-2}$ くらいの絶対誤差のある値どうしの演算結果が $10 ^ 4$ 以下の値になった場合、相対誤差が $10 ^ {-6}$ 以下であることを保証するのは難しいです。

逆に、演算結果が $4.5\times 10 ^ 6+\varepsilon$ 以上なら OK とかも言えそうな感じがしますよね（$\dfrac1D\sum x _ i ^ 2$ や $\left(\dfrac1D\sum x _ i\right) ^ 2$ は $2.25\times10 ^ {18}$ とかでおさえられるはずなので）実際、答えが $4.5\times 10 ^ 6+10$ 以下っぽいときは abort するようにすると、それ以外のケースでは AC することを確認できます（このことはこの評価がバグっていないことを意味しません。誤差が偶然いいかんじになっているかもしれないので）。

atcoder.jp