13

10^(-15)に小さな (約) 倍精度数の配列があるとします。たとえば、この配列の数値の合計を順番に計算するとします。

double sum = 0;
for (int i = 0; i < n; i++) sum+=array[i];

値が得られますx。

しかし、配列をいくつかの部分に分割し、各部分の合計を計算し、その後、すべての部分合計を合計するとx2、近い値になりますxが正確ではありませんx。そのため、合計を計算する際の正確性が失われました。

精度を失うことなく、これらの数値をいくつかの部分に分割することにより、小さな double 数値の合計を計算する方法を知っている人はいますか?

4

8 に答える 8

19

カハン総和の使用:

#include <numeric>
#include <iostream>
#include <vector>

struct KahanAccumulation
{
    double sum;
    double correction;
};

KahanAccumulation KahanSum(KahanAccumulation accumulation, double value)
{
    KahanAccumulation result;
    double y = value - accumulation.correction;
    double t = accumulation.sum + y;
    result.correction = (t - accumulation.sum) - y;
    result.sum = t;
    return result;
}

int main()
{
    std::vector<double> numbers = {0.01, 0.001, 0.0001, 0.000001, 0.00000000001};
    KahanAccumulation init = {0};
    KahanAccumulation result =
        std::accumulate(numbers.begin(), numbers.end(), init, KahanSum);

    std::cout << "Kahan Sum: " << result.sum << std::endl;
    return 0;
}

出力：

Kahan Sum: 0.011101

コードはこちら。

于 2012-04-26T09:39:49.160 に答える
4

数値の絶対サイズは問題ではありません。

より正確な合計が必要な場合は、補償された合計を検討しましたか? http://en.wikipedia.org/wiki/Kahan_summation_algorithm

ただし、正確性を失わずに本当に意味がある場合、結果は必ずしも double に収まるとは限りません。これが本当に必要な場合は、 http://dl.acm.org/citation.cfm? id=1824815などでアルゴリズム 908 を参照してください。

于 2012-04-26T09:04:30.383 に答える
3

このような場合の秘訣は、最初に配列を小さいものから大きいものに並べ替えてから、作成したサイクルで合計することです。そうすれば、精度は最高です。

Kahan総和アルゴリズムも確認できます

于 2012-04-26T08:51:34.670 に答える
2

セット全体または各サブセットの両方にカハン総和アルゴリズムを適用することを検討してください。

あなたを助けることができるこのアルゴリズムを参照する他の質問があります

于 2012-04-26T08:55:39.817 に答える
1

コンピューターの倍数は、2 進数システムで格納されます。そのため、(10 進表記で) double 値を表示すると、実際には double 値が丸められて表示されます (たとえば、0.1 は無限小数です)。double 値が 2 の次数 (たとえば 2^(-30)) である同じ実験を行うと、値が一致することがわかります。

異なる順序で double 値を合計すると違いが観察される理由は、各計算の後、結果が 2 進数値システムで丸められるため、実際の値とのわずかな違いが現れるためです。

于 2012-04-26T08:50:47.050 に答える
1

10 進数を表すために使用される 2 進浮動小数点数は、精度よりも精度が高くなります。違いを浮き彫りにする 1 つの方法を見つけました。

于 2012-04-26T08:50:53.763 に答える
1

個々の合計が最適化され、80 ビットのレジスタで実行された後、64 の double に戻された可能性があります (コンパイラ スイッチについて読んでください) 。当然、これは精度を失います。この場合、配列を分割して個々の 64 ビットの合計を加算すると、それらすべてを 80 ビットとして加算して総計を元に戻すのとは異なる答えが得られます。

これが理由ではないかもしれませんが、さらに調査する価値があるかもしれません。この質問に対する選択された答えを見てください

于 2012-04-26T09:03:35.950 に答える
0

数値を加算した結果の精度の損失は、通常のサイズの数値の処理から非常に小さな数値を処理する場合と同じです。関連する可能性があるのは次のとおりです。a）数値間のサイズの相対的な違いは大きいですか？b) 数字の記号が異なっていますか?

最後の問題は通常、加算精度で問題になります。あなたがすべきこと - 完全に最適ではないかもしれませんが、公正なショットで実装が簡単です - は次のとおりです。

a）それらをそれぞれポジティブとネガティブのサブセットに分割します

b) 各サブセットを並べ替える

それで

c) 結合された 2 つのセットから最大 (絶対サイズ) を取得し、その数値で合計を初期化し、リストから削除します。

d) 反復: 現在の合計が正の場合は常に、残りの負の最大値を取り、それを合計に追加し、リストから削除します。現在の合計が負の場合は常に、同様に行います。

このようにして、本質的に避けられない精度の損失を (ほぼ) 最小限に抑えることができる可能性がかなり高くなります (数値の表示を考えると)。

于 2012-09-06T12:49:28.867 に答える