Was ist ein guter Weg, um eine große Anzahl von kleinen Schwimmern hinzuzufügen?

Question

Angenommen, Sie haben 100000000 32-Bit Gleitkommawerte in einem Array, und jeder dieser Gleitkommazahlen hat einen Wert zwischen 0.0 und 1.0. Wenn Sie versucht haben, sie alle ähnliche

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

zu summieren würden Sie Probleme wie result bekommt viel größer als 1,0 ist.

Was sind also einige Möglichkeiten, die Summierung genauer durchzuführen?

Answer 1

Klingt wie Sie Kahan Summation verwenden möchten.

Wikipedia Laut,

Die Kahan Summenalgorithmus (auch als Summierung kompensierte bekannt) reduziert signifikant die numerischen Fehler in der eine Folge von endlicher Genauigkeit Gleitkommazahlen erhaltenen Summe durch Addieren Vergleich zu dem offensichtlichen Ansatz. Dies geschieht durch eine separate Laufkompensation (eine Variable, um kleine Fehler zu akkumulieren).

In Pseudo-Code, der Algorithmus ist:

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 

Answer 2

Machen Sie das Ergebnis zu einem Doppel, angenommen C oder C++.

Answer 3

Wenn in .NET mit der LINQ .Sum() - Erweiterungsmethode, die auf einem IEnumerable vorhanden ist. Dann wäre es nur sein:

var result = array.Sum(); 

Answer 4

Wenn Sie ein wenig mehr Platz tolerieren kann (in 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]; 

Standard-Teile-und-Herrsche-Algorithmus, im Grunde. Dies funktioniert nur, wenn die Zahlen zufällig verstreut sind; Es wird nicht funktionieren, wenn die erste halbe Milliarde Zahlen 1e-12 und die zweite halbe Milliarde viel größer sind.

Aber vorher könnte man das Ergebnis einfach verdoppeln. Das wird viel helfen.

Answer 5

Der absolut optimale Weg ist, eine Prioritätswarteschlange zu verwenden, in der folgenden Art und Weise:

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(); 

(Dieser Code übernimmt die Zahlen positiv sind, im allgemeinen der Warteschlange sollte durch absoluten Wert bestellt werden)

Erklärung: Angesichts einer Liste von Zahlen, um sie so genau wie möglich zu addieren, sollten Sie danach streben, die Zahlen zu schließen, ti eliminiere den Unterschied zwischen kleinen und großen. Deshalb wollen Sie die beiden kleinsten Zahlen addieren und so den Minimalwert der Liste erhöhen, den Unterschied zwischen dem Minimum und Maximum in der Liste verringern und die Problemgröße um 1 reduzieren.

Leider habe ich keine Ahnung Wie kann dies vektorisiert werden, wenn man bedenkt, dass Sie OpenCL verwenden. Aber ich bin mir fast sicher, dass es so sein kann. Sie können sich das Buch über Vektoralgorithmen ansehen, es ist überraschend, wie mächtig sie tatsächlich sind: Vector Models for Data-Parallel Computing