3 つの 32 ビット浮動小数点値 、a、bおよびcがあるとし(a + b) + c != a + (b + c)ます。これらの値が任意の順序で合計され、常にまったく同じ (かなり正確な) 合計になることを保証する、おそらくKahan summationに似た合計アルゴリズムはありますか? 私は一般的なケースを探しています (つまり、3 つの数字のみを扱うソリューションではありません)。
任意精度演算が唯一の方法ですか? 私は非常に大きなデータセットを扱っているので、可能であれば任意精度の演算を使用するオーバーヘッドを避けたいと思っています。
ありがとう！
ここに興味深い「全精度合計」アルゴリズムがあり、最終的な合計が被加数の順序に依存しないことを保証します (レシピは Python で提供されていますが、他の言語に翻訳するのはそれほど難しくありません)。そのリンクに示されているレシピは完全に正しいわけではないことに注意してください。メインの累積ループは問題ありませんが、累積された部分合計のリストを単一の浮動小数点結果に変換する最後のステップ (msumレシピの最後の行) )、正しく丸められた結果を得るには、部分和を単純に合計するよりも少し注意が必要です。これを修正する方法については、レシピの下のコメントと Python の実装 (以下にリンク) を参照してください。
部分和を保持するために任意精度演算の形式を使用します (中間和は double の「重複しない」和として表されます) が、特にすべての入力がほぼ同じ大きさである場合は、十分に高速である可能性があります。また、常に正しく丸められた結果が得られるため、期待どおりの精度が得られ、最終的な合計は被加数の順序に依存しません。これは、Jonathan Shewchuk によるこの論文(Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates) に基づいています。
Python はこのアルゴリズムを math.fsum の実装に使用します。これは正しく丸められた順序に依存しない合計を行います。ここで Python が使用する C 実装を確認できます--- math_fsum 関数を探してください。
合計しなければならない項に関する追加情報があれば、Shewchuk のアルゴリズムのオーバーヘッドを回避できます。
IEEE 754 算術でx-yは、 はいつでも正確ですy/2 <= x <= 2*y(Sterbenz の定理、ここで正式に証明されています)
したがって、各部分和が上記の形式になるようにすべての項を並べ替えることができれば、正確な結果が無料で得られます。
残念ながら、実際には、これが確実に発生する状況にある可能性はほとんどありません。正の数と負の数が交互に大きくなっていくのは、それが起こる 1 つのケースかもしれません。
注: 元の質問は、合計順序に関係なく同じ結果が得られるアルゴリズムに関するものでした。マークの答えは「正確なアルゴリズム」の方向へのドリフトを開始しましたが、あなたの質問をもう一度読んで、用語を並べ替えることを提案しているときに物事を押しすぎているのではないかと心配しています. おそらくあなたがやろうとしていることはできません。私の答えはおそらくトピックから外れています。すみません:)
プログラムで算術演算を行うときに (a + b) + c != a + (b + c) であるかどうかはよくわかりません。
ただし、現在のハードウェアで浮動小数点演算を使用する場合の経験則は、等しいかどうかを直接テストしないことです。
どのようなアプリケーションでも、十分に小さいイプシロンを選択して使用する必要があります
(abs(a - b) < epsilon)
平等テストとして。