私のプログラムでは、約50,000個の浮動小数点数の配列が維持されます。これらの数値の合計は重要な量であり、配列要素が変更されると最新の状態に保たれなければなりません。そこnumbersが配列である場合には、これを行うための明白な方法であり、totalはその合計である：多数の浮動小数点数の合計
function update_number(int index, float new_value) {
total += new_value - numbers[index];
numbers[index] = new_value;
}
私は真の合計に比べて価値totalのドリフトをもたらす点丸め誤差浮動心配です。これはどれくらいの問題ですか？
できるだけ正確に多数の浮動小数点を合計する最もよく知られたアルゴリズムは、Kahan summationとして知られています。アルゴリズムは加重を変更できるように書かれていませんが、適応するのは簡単です。最初の合計を計算した後は、実行中のエラー値を保持しておき、前の値の否定を加算して新しい値を加算して合計を更新してください。
残念ながら、あなたの数字の多くが負の数である場合、カハンの和は大きな最悪の場合の保証を提供しません...そして、更新手順によって、そのことが保証されます。 （実際には、条件数が十分に更新された後に0になる傾向があります。つまり、エラーが無制限になることを意味します）はKahan集計を使用し、エラーは、おそらくと小さくなります。それ。
さらに良い選択肢はpairwise summationであり、実際には非常に高い精度を提供します。ペアワイズ加算では、配列の最初と最後の半分のペアワイズ和を再帰的に求め、その結果を合計します。それは、2つの子ノードの合計を保持する内部ノードと、すべての葉の合計を保持するルートを持つ、2進木と考えることができます。
更新可能なアルゴリズムにペアごとの合計を作成するには、すべてのツリーノードを周りに保つだけです。更新された値ごとに、ターゲットリーフを変更し、その祖先をすべてルートに戻して再計算します。更新1回につき合計がlog2(n)で、それ以上の値はnとなります。