[解決済み] 最も正確な結果を得るためには、どのような順序でフロートを追加すればよいのでしょうか？

どのように解決するのですか？

あなたの直感は基本的に正しく、（大きさの）昇順でソートすると、通常は多少改善されます。単精度 (32 ビット) 浮動小数点を加算する場合を考えてみましょう。1 / (10 億) に等しい値が 10 億個あり、1 に等しい値が 1 つあります。1 が最初に来た場合、精度の損失により 1 + (1 / 10 億) が 1 になるので、合計は 1 になります。それぞれの足し算は合計にまったく影響を与えません。

小さな値が最初に来る場合、少なくとも合計は何かになりますが、それでも 2^30 個の値があり、2^25 ほど経過すると、それぞれが個別に合計に影響を及ぼさない状況に戻ってしまいます。だから、もっとトリックが必要なんだ。

これは極端な例ですが、一般に、大きさが非常に異なる 2 つの値を加算するよりも、大きさが同じ 2 つの値を加算する方が正確です。数字を並べ替えることで、同じような大きさの値をグループ化し、昇順で加算することで、小さな値にも大きな値の大きさに累積的に到達する「チャンス」を与えることができるのです。

しかし、負の数が含まれる場合、この方法を裏切るのは簡単です。合計する 3 つの値を考えてみましょう。 {1, -1, 1 billionth} . 算術的に正しい和は 1 billionth となりますが、最初の足し算に小さな値が含まれていると、最終的な和は 0 になります。 6 つの可能な順序のうち、2 つだけが "正しい順序です -。 {1, -1, 1 billionth} と {-1, 1, 1 billionth} . 6つのオーダーはすべて、入力の中で最も大きな値のスケールで正確な結果（0.0000001% out）を与えますが、そのうちの4つは真の解のスケールで不正確な結果（100% out）です。前者が十分であるかどうかは、あなたが解決しようとしている特定の問題によってわかります。

実際には、ただソートして足すだけでなく、もっとたくさんのトリックを行うことができます。非常に小さな値がたくさんあり、中間の値があり、大きな値が少ない場合、まず小さな値をすべて合計し、次に中間の値を別々に合計し、その 2 つの合計を合わせてから大きな値を追加するのが最も正確な方法かもしれません。浮動小数点数の足し算の最も正確な組み合わせを見つけるのは簡単ではありませんが、本当に悪いケースに対処するために、異なる大きさの実行合計の配列をすべて保持しておき、新しい値をその大きさに最も合う合計に加えます。実行合計がその大きさに対して大きくなり始めたら、それを次の合計に加え、新しいものを始めることができます。論理的に極端に言えば、この処理は任意精度の型で合計を実行することと同じです（だから、そうするのでしょう）。しかし、大きさの昇順または降順で追加するという単純な選択を考えると、昇順のほうが有利です。

なぜなら、それぞれが個別に合計に影響を与えるには小さすぎる多数の値からなる「重い」尾部を誤って切り落としたり、個別に合計の最後の数ビットにしか影響しない多くの小さな値の精度を捨てたりすると、計算が非常に悪くなるケースがいくつかあるからです。末尾が無視できるようなケースでは、おそらく気にする必要はないでしょう。例えば、最初の段階で少数の値しか加算しておらず、合計の有効数字数個しか使っていない場合などです。