Memo

Twitterに書くには長すぎることを書きます。Opinions are my own.

偏角ソートにおけるdoubleとlong doubleの精度について

幾何の問題だと偏角ソートしたくなることがよくあって、その場合に std::atan2 を使うことが多い。ここでいつ long double が必要になるかというメモ。

結論

x座標とy座標の値が整数で区間 [-109, 109] に含まれる場合はlong doubleを使う。 [-105, 105] の場合はdoubleでも大丈夫。long doubleがない言語で [-109, 109] に対応しようとすると、単純に atan2 のような関数を使うだけでは駄目で内積と外積を使う必要がある(自信がない)。

-> この結論は微妙に正しくないので、追記も見てください

doubleでは駄目な場合

コード

      int x1 = 1e+9, y1 = 1e+9-1;
      int x2 = x1-1, y2 = y1-1;

      double tan1 = atan2((double)y1, (double)x1);
      double tan2 = atan2((double)y2, (double)x2);

      cout << setprecision(20) << fixed;

      cout << tan1 << endl;
      cout << tan2 << endl;

      long double tan1ld = atan2((long double)x1, (long double)y1);
      long double tan2ld = atan2((long double)x2, (long double)y2);

      cout << tan1ld << endl;
      cout << tan2ld << endl;

出力

0.78539816289744834865
0.78539816289744834865
0.78539816389744830985
0.78539816389744831034

doubleでもよい場合

コード

      int x1 = 1e+5, y1 = 1e+5-1;
      int x2 = x1-1, y2 = y1-1;

      double tan1 = atan2((double)y1, (double)x1);
      double tan2 = atan2((double)y2, (double)x2);

      cout << setprecision(20) << fixed;

      cout << tan1 << endl;
      cout << tan2 << endl;

出力

0.78539316337244824417
0.78539316332244724084

long doubleで解ける問題

追記

LayCurseさんからご指摘がありました

ざっくりまとめると、以下の通り

  • https://ideone.com/g0Fso7 にある通り、long doubleで表される数の2つ隣の値が出ることがあるため +2PIして比較はうまくいきそうだが +4PIして比較は駄目そう
  • また、原点を中心としない場合は 2*109 まで考えないといけないので、これだとlong doubleで+2PIして比較も怪しい
  • AtCoderならboostが使えるので、boostの多倍長浮動小数点数を使ってゴリ押せる可能性がある (AtCoderで誤差が厳しい系の問題はそもそも出ない気がするけど)