¿Cuál es una buena manera de agregar una gran cantidad de flotadores pequeños juntos?

Question

Digamos que tiene 100000000 valores de punto flotante de 32 bits en una matriz, y cada uno de estos flotantes tiene un valor entre 0.0 y 1.0. Si se trató de resumirlas como esto

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

que te llegas a tener problemas como result se hace mucho mayor que 1,0.

¿Cuáles son algunas de las maneras de realizar la suma de manera más precisa?

Answer 1

suena como usted desea utilizar Kahan Summation.

Según Wikipedia,

El Kahan algoritmo de suma (también conocido como suma compensada) reduce significativamente el error numérico en el total obtenido por adición de una secuencia de números de punto precisión finita flotantes, comparado al enfoque obvio. Esto se hace manteniendo una compensación de ejecución separada (una variable para acumular pequeños errores).

En pseudocódigo, el algoritmo es:

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

Haga que el resultado sea doble, suponiendo C o C++.

Answer 3

Si está en .NET utilizando el método de extensión LINQ .Sum() que existe en un IEnumerable. A continuación, sólo sería:

var result = array.Sum(); 

Answer 4

Si se puede tolerar un poco más de espacio (en 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]; 

algoritmo divide y vencerás Estándar, básicamente. Esto solo funciona si los números están aleatoriamente dispersos; no funcionará si los primeros 500 millones son 1e-12 y los segundos 500 millones son mucho más grandes.

Pero antes de hacer nada de eso, uno podría simplemente acumular el resultado en un doble. Eso ayudará mucho.

Answer 5

La forma absolutamente óptimo es el uso de una cola de prioridad, de la siguiente manera:

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

(este código se supone que los números son positivos; generalmente la cola deben ser ordenados por valor absoluto)

Explicación: dada una lista de números, para sumarlos de la manera más precisa posible, debe esforzarse por hacer que los números eliminar la diferencia entre los pequeños y grandes. Es por eso que desea sumar los dos números más pequeños, aumentando así el valor mínimo de la lista, disminuyendo la diferencia entre el mínimo y el máximo en la lista y reduciendo el tamaño del problema en 1.

Lamentablemente no tengo ni idea cómo se puede vectorizar, teniendo en cuenta que estás usando OpenCL. Pero estoy casi seguro de que puede ser. Puede echar un vistazo al libro sobre algoritmos vectoriales, es sorprendente lo poderosos que son en realidad: Vector Models for Data-Parallel Computing