12

配列に100000000個の32ビット浮動小数点値があり、これらの各浮動小数点数の値が0.0〜1.0であるとします。あなたがそれらをすべてこのように合計しようとした場合

result = 0.0;
for (i = 0; i < 100000000; i++) {
    result += array[i];
}

result1.0よりもはるかに大きくなると、問題が発生します。

では、合計をより正確に実行する方法にはどのようなものがありますか？

4

5 に答える 5

30

カハンの加算を使用したいようです。

ウィキペディアによると、

カハンの加算アルゴリズム（補償された加算とも呼ばれます）は、明白なアプローチと比較して、有限精度の浮動小数点数のシーケンスを追加することによって得られる合計の数値誤差を大幅に削減します。これは、個別の実行補償（小さなエラーを累積するための変数）を保持することによって行われます。

擬似コードでは、アルゴリズムは次のとおりです。

function kahanSum(input)
 var sum = input[1]
 var c = 0.0          //A running compensation for lost low-order bits.
 for i = 2 to input.length
  y = input[i] - c    //So far, so good: c is zero.
  t = sum + y         //Alas, sum is big, y small, so low-order digits of y are lost.
  c = (t - sum) - y   //(t - sum) recovers the high-order part of y; subtracting y recovers -(low part of y)
  sum = t             //Algebraically, c should always be zero. Beware eagerly optimising compilers!
 next i               //Next time around, the lost low part will be added to y in a fresh attempt.
return sum
于 2010-03-16T16:58:09.253 に答える
1

CまたはC++を想定して、結果をdoubleにします。

于 2010-03-16T16:52:21.463 に答える
1

（Javaで）少し余分なスペースを許容できる場合：

float temp = new float[1000000];
float temp2 = new float[1000];
float sum = 0.0f;
for (i=0 ; i<1000000000 ; i++) temp[i/1000] += array[i];
for (i=0 ; i<1000000 ; i++) temp2[i/1000] += temp[i];
for (i=0 ; i<1000 ; i++) sum += temp2[i];

基本的に、標準の分割統治アルゴリズム。これは、数字がランダムに散らばっている場合にのみ機能します。前半の10億の数字が1e-12で、後半の10億の数字がはるかに大きい場合は、機能しません。

しかし、それを行う前に、結果を2倍に累積するだけかもしれません。それは大いに役立ちます。

于 2010-03-16T17:30:50.757 に答える
0

.NETで、IEnumerableに存在するLINQ .Sum（）拡張メソッドを使用している場合。次に、それは次のようになります。

var result = array.Sum();
于 2010-03-16T16:57:23.770 に答える
0

絶対に最適な方法は、次のように優先キューを使用することです。

PriorityQueue<Float> q = new PriorityQueue<Float>();
for(float x : list) q.add(x);
while(q.size() > 1) q.add(q.pop() + q.pop());
return q.pop();

（このコードは、数値が正であることを前提としています。通常、キューは絶対値で並べ替える必要があります）

説明：数字のリストが与えられた場合、それらをできるだけ正確に合計するには、数字を近づけるように努力する必要があります。小さい数字と大きい数字の違いをなくします。そのため、最小の2つの数値を合計して、リストの最小値を増やし、リストの最小値と最大値の差を減らし、問題のサイズを1つ減らします。

残念ながら、OpenCLを使用していることを考えると、これをどのようにベクトル化できるかわかりません。しかし、私はそれが可能であるとほぼ確信しています。あなたはベクトルアルゴリズムに関する本を見る​​かもしれません、それはそれらが実際にどれほど強力であるか驚くべきことです：データのためのベクトルモデル-並列計算

于 2010-03-17T08:28:55.647 に答える