Quel est le meilleur moyen d'ajouter un grand nombre de petits flotteurs ensemble?

Question

Supposons que vous ayez des valeurs à virgule flottante 32 bits de 100000000 dans un tableau et que chacune de ces valeurs flottantes ait une valeur comprise entre 0,0 et 1,0. Si vous avez essayé de les résumer tout comme ça

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

vous auriez un problème comme result devient beaucoup plus grand que 1,0.

Alors, quelles sont certaines des façons d'effectuer plus précisément la sommation?

Answer 1

On dirait que vous voulez utiliser Kahan Summation.

Selon Wikipedia,

Le algorithme de sommation Kahan (également connu sous le nom sommation compensée) réduit sensiblement l'erreur numérique dans le total obtenu par l'addition d'une séquence de nombres à virgule flottante précision finie, comparativement à l'approche évidente. Ceci est fait en gardant une compensation de fonctionnement séparée (une variable pour accumuler de petites erreurs).

En pseudocode, l'algorithme est:

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

Rend le résultat un double, en supposant C ou C++.

Answer 3

Si .NET en utilisant la méthode d'extension LINQ .Sum() qui existe sur un IEnumerable. Ensuite, il serait tout simplement:

var result = array.Sum(); 

Answer 4

Si vous pouvez tolérer un peu plus d'espace (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]; 

algorithme diviser pour mieux régner Standard, essentiellement. Cela ne fonctionne que si les nombres sont dispersés au hasard; cela ne fonctionnera pas si le premier demi-milliard de numéros est 1e-12 et le second demi-milliard est beaucoup plus grand.

Mais avant de faire cela, on pourrait simplement accumuler le résultat en double. Ça va beaucoup aider.

Answer 5

La façon tout à fait optimale consiste à utiliser une file d'attente de priorité, de la manière suivante:

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

(Ce code suppose que les chiffres sont positifs, généralement la file d'attente doivent être commandés par la valeur absolue)

Explication: à partir d'une liste de nombres, pour les additionner aussi précisément que possible, vous devriez vous efforcer de rapprocher les chiffres, ti éliminer la différence entre les petits et les grands. C'est pourquoi vous voulez ajouter les deux plus petits nombres, augmentant ainsi la valeur minimale de la liste, diminuant la différence entre le minimum et le maximum dans la liste et réduisant la taille du problème par 1.

Malheureusement je n'ai aucune idée de comment cela peut être vectorisé, sachant que vous utilisez OpenCL. Mais je suis presque sûr que cela peut être. Vous pourriez jeter un coup d'oeil sur le livre sur les algorithmes vectoriels, il est surprenant de voir à quel point ils sont puissants: Vector Models for Data-Parallel Computing