Qual è un buon modo per aggiungere un gran numero di piccoli oggetti galleggianti?

Question

Supponiamo di avere 100000000 valori in virgola mobile a 32 bit in un array e ognuno di questi float ha un valore compreso tra 0.0 e 1.0. Se si è tentato di riassumere tutti in su come questo

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

che ci si esegue in problemi come result ottiene molto più grande di 1,0.

Quindi quali sono alcuni dei modi per eseguire la sommatoria in maniera più accurata?

Answer 1

Suona come si desidera utilizzare Kahan Summation.

Secondo Wikipedia,

Il Kahan algoritmo somma (noto anche come sommatoria compensato) riduce significativamente l'errore numerico nel totale ottenuta aggiungendo una sequenza di numeri in virgola precisione finita galleggiamento, rispetto all'approccio ovvio. Questo viene fatto mantenendo una compensazione di corsa separata (una variabile per accumulare piccoli errori).

In pseudocodice, l'algoritmo è:

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

Rendere un risultato doppio, presupponendo C o C++.

Answer 3

Se in .NET si utilizza il metodo di estensione LINQ .Sum() esistente su un oggetto IEnumerable. Poi sarebbe solo:

var result = array.Sum(); 

Answer 4

Se si può tollerare un po 'di spazio in più (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 algoritmo divide et impera, in fondo. Funziona solo se i numeri sono sparsi casualmente; non funzionerà se il primo mezzo miliardo di numeri è 1e-12 e il secondo mezzo miliardo è molto più grande.

Ma prima di fare qualsiasi cosa, si potrebbe semplicemente accumulare il risultato in un doppio. Questo aiuterà molto.

Answer 5

Il modo assolutamente ottimale è quello di utilizzare una coda di priorità, nel seguente modo:

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

(questo codice assume i numeri sono positivi, generalmente coda devono essere ordinati in valore assoluto)

Spiegazione: dato un elenco di numeri, per aggiungerli nel modo più preciso possibile, dovresti cercare di chiudere i numeri, ti eliminare la differenza tra piccoli e grandi. Ecco perché vuoi sommare i due numeri più piccoli, aumentando così il valore minimo della lista, diminuendo la differenza tra il minimo e il massimo nell'elenco e riducendo la dimensione del problema di 1.

Purtroppo non ho idea di come questo può essere vettorializzato, considerando che stai usando OpenCL. Ma sono quasi sicuro che possa essere. Potresti dare un'occhiata al libro sugli algoritmi vettoriali, è sorprendente quanto siano potenti in realtà: Vector Models for Data-Parallel Computing