Dans quel ordre les flotteurs doivent-ils être ajoutés pour obtenir le résultat le plus précis?

105

C'est une question qui m'a été posée lors de mon récent entretien et que je veux savoir (je ne me souviens pas vraiment de la théorie de l'analyse numérique, alors aidez-moi :)

Si nous avons une fonction, qui accumule des nombres à virgule flottante:

std::accumulate(v.begin(), v.end(), 0.0);

vest un std::vector<float>, par exemple.

  • Serait-il préférable de trier ces nombres avant de les accumuler?

  • Quel ordre donnerait la réponse la plus précise?

Je soupçonne que le tri des nombres en ordre croissant serait en fait faire l'erreur numérique moins , mais malheureusement je ne peux pas le prouver moi - même.

PS Je me rends compte que cela n'a probablement rien à voir avec la programmation du monde réel, juste être curieux.

Yippie-Ki-Yay
la source
17
Cela a en fait tout à voir avec la programmation du monde réel. Cependant, de nombreuses applications ne se soucient pas vraiment de la meilleure précision absolue du calcul tant qu'il est «assez proche». Applications d'ingénierie? Extrêmement important. Applications médicales? Extrêmement important. Statistiques à grande échelle? Un peu moins de précision est acceptable.
Zéychin le
18
Veuillez ne pas répondre à moins que vous ne sachiez réellement et que vous puissiez pointer vers une page qui explique en détail votre raisonnement. Il y a déjà tellement de conneries à propos des nombres à virgule flottante qui volent autour que nous ne voulons pas y ajouter. Si vous pensez que vous savez. ARRÊTEZ. parce que si vous pensez seulement savoir, vous vous trompez probablement.
Martin York
4
@ Zéychin "Applications d'ingénierie? Extrêmement importantes. Applications médicales? Extrêmement importantes." ??? Je pense que vous seriez surpris si vous saviez la vérité :)
BЈовић
3
@Zeychin L'erreur absolue n'est pas pertinente. Ce qui est important, c'est l'erreur relative. Si quelques centièmes de radian valent 0,001%, alors qui s'en soucie?
BЈовић le
3
Je recommande vraiment cette lecture: "ce que tout informaticien doit savoir sur la virgule flottante" perso.ens-lyon.fr/jean-michel.muller/goldberg.pdf
Mohammad Alaggan

Réponses:

108

Votre instinct a fondamentalement raison, le tri par ordre croissant (de grandeur) améliore généralement quelque peu les choses. Prenons le cas où nous ajoutons des flottants à simple précision (32 bits), et il y a 1 milliard de valeurs égales à 1 / (1 milliard), et une valeur égale à 1. Si le 1 vient en premier, alors la somme viendra à 1, car 1 + (1/1 milliard) est égal à 1 en raison d'une perte de précision. Chaque ajout n'a aucun effet sur le total.

Si les petites valeurs viennent en premier, elles totaliseront au moins quelque chose, même si même dans ce cas j'en ai 2 ^ 30, alors qu'après 2 ^ 25 environ, je suis de retour dans la situation où chacune individuellement n'affecte pas le total plus. Je vais donc encore avoir besoin de plus de trucs.

C'est un cas extrême, mais en général, l'ajout de deux valeurs d'amplitude similaire est plus précis que l'ajout de deux valeurs d'amplitudes très différentes, car vous «rejetez» moins de bits de précision dans la valeur la plus petite de cette façon. En triant les nombres, vous regroupez des valeurs de grandeur similaire et en les additionnant par ordre croissant, vous donnez aux petites valeurs une "chance" d'atteindre cumulativement la grandeur des plus grands nombres.

Pourtant, si des nombres négatifs sont impliqués, il est facile de «déjouer» cette approche. Tenez compte trois valeurs à somme, {1, -1, 1 billionth}. La somme arithmétiquement correcte est 1 billionth, mais si mon premier ajout implique la valeur minuscule, ma somme finale sera 0. Sur les 6 ordres possibles, seuls 2 sont "corrects" - {1, -1, 1 billionth}et{-1, 1, 1 billionth} . Tous les 6 ordres donnent des résultats qui sont précis à l'échelle de la valeur de plus grande magnitude de l'entrée (0,0000001% en sortie), mais pour 4 d'entre eux, le résultat est inexact à l'échelle de la vraie solution (100% en sortie). Le problème particulier que vous résolvez vous dira si le premier est assez bon ou non.

En fait, vous pouvez jouer beaucoup plus de tours que de simplement les ajouter dans un ordre trié. Si vous avez beaucoup de très petites valeurs, un nombre moyen de valeurs moyennes et un petit nombre de grandes valeurs, alors il peut être plus précis d'additionner d'abord toutes les petites, puis additionner séparément les moyennes, additionner ces deux totaux puis ajoutez les gros. Il n'est pas du tout trivial de trouver la combinaison la plus précise d'ajouts en virgule flottante, mais pour faire face à de très mauvais cas, vous pouvez conserver tout un tableau de totaux cumulés à différentes magnitudes, ajouter chaque nouvelle valeur au total qui correspond le mieux à son ampleur, et lorsqu'un total cumulé commence à devenir trop grand pour son ampleur, ajoutez-le au total suivant et commencez-en un nouveau. Pris à son extrême logique, ce processus équivaut à effectuer la somme dans un type à précision arbitraire (donc vous d faire ça). Mais étant donné le choix simpliste de l'addition par ordre de grandeur croissant ou décroissant, le meilleur pari est de monter.

Il a une certaine relation avec la programmation du monde réel, car il y a des cas où votre calcul peut aller très mal si vous coupez accidentellement une queue "lourde" composée d'un grand nombre de valeurs dont chacune est trop petite pour être affectée individuellement la somme, ou si vous jetez trop de précision à un grand nombre de petites valeurs qui n'affectent individuellement que les derniers bits de la somme. Dans les cas où la queue est négligeable de toute façon, vous ne vous en souciez probablement pas. Par exemple, si vous additionnez seulement un petit nombre de valeurs au départ et que vous n'utilisez que quelques chiffres significatifs de la somme.

Steve Jessop
la source
8
+1 pour l'explication. Ceci est quelque peu contre-intuitif car l'addition est généralement numériquement stable (contrairement à la soustraction et à la division).
Konrad Rudolph le
2
@Konrad, il peut être numériquement stable, mais ce n'est pas précis étant donné les différentes magnitudes des opérandes :)
MSN
3
@ 6502: ils sont triés par ordre de grandeur, donc le -1 vient à la fin. Si la valeur réelle du total est de magnitude 1, c'est très bien. Si vous additionnez trois valeurs: 1 / milliard, 1 et -1, alors vous obtiendrez 0, à quel point vous devez répondre à la question pratique intéressante - avez-vous besoin d'une réponse exacte à l'échelle du somme vraie, ou avez-vous seulement besoin d'une réponse précise à l'échelle des plus grandes valeurs? Pour certaines applications pratiques, ce dernier est assez bon, mais quand ce n'est pas le cas, vous avez besoin d'une approche plus sophistiquée. La physique quantique utilise la renormalisation.
Steve Jessop le
8
Si vous voulez vous en tenir à ce schéma simple, j'ajouterais toujours les deux nombres avec la plus faible magnitude et réinsérerais la somme dans l'ensemble. (Eh bien, probablement un tri de fusion fonctionnerait mieux ici. Vous pouvez utiliser la partie du tableau contenant les nombres précédemment additionnés comme zone de travail pour les sommes partielles.)
Neil
2
@Kevin Panko: La version simple est qu'un flotteur simple précision a 24 chiffres binaires, dont le plus grand est le plus grand bit défini du nombre. Donc, si vous additionnez deux nombres dont la grandeur diffère de plus de 2 ^ 24, vous subissez une perte totale de la valeur la plus petite, et s'ils diffèrent en grandeur d'un degré plus petit, vous perdez un nombre correspondant de bits de précision du plus petit. nombre.
Steve Jessop le
88

Il existe également un algorithme conçu pour ce type d'opération d'accumulation, appelé Kahan Summation , dont vous devriez probablement être conscient.

Selon Wikipedia,

L' algorithme de sommation de Kahan (également connu sous le nom de sommation compensée ) réduit considérablement l'erreur numérique dans le total obtenu en ajoutant une séquence de nombres à virgule flottante de précision finie, par rapport à l'approche évidente. Cela se fait en conservant une compensation de fonctionnement distincte (une variable pour accumuler les 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
Daniel Pryden
la source
3
+1 belle addition à ce fil. Tout compilateur qui "optimise avidement" ces instructions doit être banni.
Chris A.
1
C'est une méthode simple pour presque doubler la précision, en utilisant deux variables de sommation sumet cde grandeur différente. Il peut être étendu de manière triviale à N variables.
MSalters
2
@ChrisA. eh bien, vous pouvez contrôler cela explicitement sur tous les compilateurs qui comptent (par exemple via -ffast-mathsur GCC).
Konrad Rudolph
6
@Konrad Rudolph merci d'avoir souligné qu'il s'agit d'une optimisation possible avec -ffast-math. Ce que j'ai appris de cette discussion et de ce lien , c'est que si vous vous souciez de la précision numérique, vous devriez probablement éviter d'utiliser, -ffast-mathmais que dans de nombreuses applications où vous pouvez être lié au processeur mais ne vous souciez pas des calculs numériques précis, (programmation de jeux par exemple ), -ffast-mathest raisonnable à utiliser. Par conséquent, je voudrais modifier mon commentaire «interdit» fortement formulé.
Chris A.
L'utilisation de variables à double précision pour sum, c, t, yaidera. Vous devez également ajouter sum -= cà avant return sum.
G. Cohen
34

J'ai essayé l'exemple extrême de la réponse fournie par Steve Jessop.

#include <iostream>
#include <iomanip>
#include <cmath>

int main()
{
    long billion = 1000000000;
    double big = 1.0;
    double small = 1e-9;
    double expected = 2.0;

    double sum = big;
    for (long i = 0; i < billion; ++i)
        sum += small;
    std::cout << std::scientific << std::setprecision(1) << big << " + " << billion << " * " << small << " = " <<
        std::fixed << std::setprecision(15) << sum <<
        "    (difference = " << std::fabs(expected - sum) << ")" << std::endl;

    sum = 0;
    for (long i = 0; i < billion; ++i)
        sum += small;
    sum += big;
    std::cout  << std::scientific << std::setprecision(1) << billion << " * " << small << " + " << big << " = " <<
        std::fixed << std::setprecision(15) << sum <<
        "    (difference = " << std::fabs(expected - sum) << ")" << std::endl;

    return 0;
}

J'ai obtenu le résultat suivant:

1.0e+00 + 1000000000 * 1.0e-09 = 2.000000082740371    (difference = 0.000000082740371)
1000000000 * 1.0e-09 + 1.0e+00 = 1.999999992539933    (difference = 0.000000007460067)

L'erreur dans la première ligne est plus de dix fois plus grande dans la seconde.

Si je change le doubles en floats dans le code ci-dessus, j'obtiens:

1.0e+00 + 1000000000 * 1.0e-09 = 1.000000000000000    (difference = 1.000000000000000)
1000000000 * 1.0e-09 + 1.0e+00 = 1.031250000000000    (difference = 0.968750000000000)

Aucune des deux réponses n'est même proche de 2,0 (mais la seconde est légèrement plus proche).

En utilisant la sommation Kahan (avec doubles) comme décrit par Daniel Pryden:

#include <iostream>
#include <iomanip>
#include <cmath>

int main()
{
    long billion = 1000000000;
    double big = 1.0;
    double small = 1e-9;
    double expected = 2.0;

    double sum = big;
    double c = 0.0;
    for (long i = 0; i < billion; ++i) {
        double y = small - c;
        double t = sum + y;
        c = (t - sum) - y;
        sum = t;
    }

    std::cout << "Kahan sum  = " << std::fixed << std::setprecision(15) << sum <<
        "    (difference = " << std::fabs(expected - sum) << ")" << std::endl;

    return 0;
}

J'obtiens exactement 2.0:

Kahan sum  = 2.000000000000000    (difference = 0.000000000000000)

Et même si je change le doubles en floats dans le code ci-dessus, j'obtiens:

Kahan sum  = 2.000000000000000    (difference = 0.000000000000000)

Il semblerait que Kahan soit la voie à suivre!

Andrew Stein
la source
Ma "grande" valeur est égale à 1 et non à 1e9. Votre deuxième réponse, ajoutée par ordre croissant de taille, est mathématiquement correcte (1 milliard, plus un milliard de milliardièmes, c'est 1 milliard et 1), bien que plus par chance aucune validité générale de la méthode :-) Notez que doublecela ne souffre pas mal perte de précision en additionnant un milliard de milliardièmes, puisqu'il a 52 bits significatifs, alors que l'IEEE floatn'en a que 24 et le ferait.
Steve Jessop le
@Steve, mon erreur, excuses. J'ai mis à jour l'exemple de code selon votre intention.
Andrew Stein du
4
Kahan a toujours une précision limitée, mais pour construire un cas de tueur, vous avez besoin à la fois de la somme principale et de l'accumulateur d'erreurs cpour contenir des valeurs beaucoup plus grandes que la sommation suivante. Cela signifie que la somme est beaucoup, beaucoup plus petite que la somme principale, donc il va falloir y en avoir énormément pour ajouter beaucoup. Surtout avec l' doublearithmétique.
Steve Jessop
14

Il existe une classe d'algorithmes qui résolvent exactement ce problème, sans qu'il soit nécessaire de trier ou de réorganiser les données .

En d'autres termes, la sommation peut être effectuée en un seul passage sur les données. Cela rend également ces algorithmes applicables dans des situations où l'ensemble de données n'est pas connu à l'avance, par exemple si les données arrivent en temps réel et que la somme en cours doit être maintenue.

Voici le résumé d'un article récent:

Nous présentons un nouvel algorithme en ligne pour la somme exacte d'un flux de nombres à virgule flottante. Par «en ligne», nous entendons que l'algorithme n'a besoin de voir qu'une seule entrée à la fois, et peut prendre un flux d'entrée de longueur arbitraire de ces entrées tout en ne nécessitant qu'une mémoire constante. Par «exact», nous entendons que la somme du tableau interne de notre algorithme est exactement égale à la somme de toutes les entrées, et le résultat renvoyé est la somme correctement arrondie. La preuve d'exactitude est valable pour toutes les entrées (y compris les nombres non normalisés mais le débordement intermédiaire modulo), et est indépendante du nombre de sommations ou du numéro de condition de la somme. L'algorithme n'a besoin asymptotiquement que de 5 FLOP par sommation, et en raison du parallélisme au niveau des instructions, il ne fonctionne que 2 à 3 fois plus lentement que l'évidence, boucle de «sommation récursive ordinaire» rapide mais stupide lorsque le nombre de sommations est supérieur à 10 000. Ainsi, à notre connaissance, c'est le plus rapide, le plus précis et le plus efficace en mémoire parmi les algorithmes connus. En effet, il est difficile de voir comment un algorithme plus rapide ou nécessitant beaucoup moins de FLOP pourrait exister sans améliorations matérielles. Une demande pour un grand nombre de sommations est fournie.

Source: Algorithme 908: Somme exacte en ligne des flux à virgule flottante .

NPE
la source
1
@Inverse: Il existe encore des bibliothèques de briques et de mortier. Alternativement, l'achat du PDF en ligne coûte 5 $ 15 $ (selon que vous êtes membre de l'ACM). Enfin, DeepDyve semble proposer de prêter le papier pendant 24 heures pour 2,99 $ (si vous êtes nouveau sur DeepDyve, vous pourrez peut-être même l'obtenir gratuitement dans le cadre de leur essai gratuit): deepdyve.com/lp/acm /…
NPE
2

En me basant sur la réponse de Steve de trier d'abord les nombres par ordre croissant, je présenterais deux autres idées:

  1. Décidez de la différence d'exposant de deux nombres au-dessus de laquelle vous pourriez décider que vous perdriez trop de précision.

  2. Additionnez ensuite les nombres dans l'ordre jusqu'à ce que l'exposant de l'accumulateur soit trop grand pour le nombre suivant, puis placez l'accumulateur dans une file d'attente temporaire et démarrez l'accumulateur avec le nombre suivant. Continuez jusqu'à ce que vous ayez épuisé la liste d'origine.

Vous répétez le processus avec la file d'attente temporaire (après l'avoir triée) et avec une différence d'exposant éventuellement plus grande.

Je pense que ce sera assez lent si vous devez calculer les exposants tout le temps.

J'ai essayé rapidement un programme et le résultat était 1.99903

quamrana
la source
2

Je pense que vous pouvez faire mieux que de trier les nombres avant de les accumuler, car pendant le processus d'accumulation, l'accumulateur devient de plus en plus gros. Si vous avez un grand nombre de nombres similaires, vous commencerez à perdre rapidement de la précision. Voici ce que je suggérerais à la place:

while the list has multiple elements
    remove the two smallest elements from the list
    add them and put the result back in
the single element in the list is the result

Bien sûr, cet algorithme sera plus efficace avec une file d'attente prioritaire au lieu d'une liste. Code C ++:

template <typename Queue>
void reduce(Queue& queue)
{
    typedef typename Queue::value_type vt;
    while (queue.size() > 1)
    {
        vt x = queue.top();
        queue.pop();
        vt y = queue.top();
        queue.pop();
        queue.push(x + y);
    }
}

chauffeur:

#include <iterator>
#include <queue>

template <typename Iterator>
typename std::iterator_traits<Iterator>::value_type
reduce(Iterator begin, Iterator end)
{
    typedef typename std::iterator_traits<Iterator>::value_type vt;
    std::priority_queue<vt> positive_queue;
    positive_queue.push(0);
    std::priority_queue<vt> negative_queue;
    negative_queue.push(0);
    for (; begin != end; ++begin)
    {
        vt x = *begin;
        if (x < 0)
        {
            negative_queue.push(x);
        }
        else
        {
            positive_queue.push(-x);
        }
    }
    reduce(positive_queue);
    reduce(negative_queue);
    return negative_queue.top() - positive_queue.top();
}

Les nombres dans la file d'attente sont négatifs car topdonne le plus grand nombre, mais nous voulons le plus petit . J'aurais pu fournir plus d'arguments de modèle à la file d'attente, mais cette approche semble plus simple.

fredoverflow
la source
2

Cela ne répond pas tout à fait à votre question, mais une chose intelligente à faire est d'exécuter la somme deux fois, une fois en mode arrondi "arrondi" et une fois avec "arrondi vers le bas". Comparez les deux réponses, et vous savez / comment / vos résultats sont inexacts, et si vous devez donc utiliser une stratégie de sommation plus intelligente. Malheureusement, la plupart des langages ne facilitent pas la modification du mode d'arrondi en virgule flottante, car les gens ne savent pas qu'il est réellement utile dans les calculs quotidiens.

Jetez un œil à l' arithmétique d'intervalle où vous faites tous les calculs comme celui-ci, en gardant les valeurs les plus élevées et les plus basses au fur et à mesure. Cela conduit à des résultats et optimisations intéressants.

rjmunro
la source
0

Le tri le plus simple qui améliore la précision consiste à trier par valeur absolue ascendante. Cela permet aux plus petites valeurs de magnitude d'avoir une chance de s'accumuler ou d'annuler avant d'interagir avec des valeurs de magnitude plus grandes qui auraient déclenché une perte de précision.

Cela dit, vous pouvez faire mieux en suivant plusieurs sommes partielles qui ne se chevauchent pas. Voici un article décrivant la technique et présentant une preuve de précision: www-2.cs.cmu.edu/afs/cs/project/quake/public/papers/robust-arithmetic.ps

Cet algorithme et d'autres approches de la sommation exacte en virgule flottante sont implémentés en Python simple à l' adresse : http://code.activestate.com/recipes/393090/ Au moins deux d'entre eux peuvent être convertis de manière simple en C ++.

Raymond Hettinger
la source
0

Pour les nombres de format simple ou double précision IEEE 754 ou de format connu, une autre alternative consiste à utiliser un tableau de nombres (transmis par l'appelant ou dans une classe pour C ++) indexés par l'exposant. Lors de l'ajout de nombres dans le tableau, seuls les nombres avec le même exposant sont ajoutés (jusqu'à ce qu'un emplacement vide soit trouvé et le nombre stocké). Lorsqu'une somme est demandée, le tableau est additionné du plus petit au plus grand pour minimiser la troncature. Exemple simple précision:

/* clear array */
void clearsum(float asum[256])
{
size_t i;
    for(i = 0; i < 256; i++)
        asum[i] = 0.f;
}

/* add a number into array */
void addtosum(float f, float asum[256])
{
size_t i;
    while(1){
        /* i = exponent of f */
        i = ((size_t)((*(unsigned int *)&f)>>23))&0xff;
        if(i == 0xff){          /* max exponent, could be overflow */
            asum[i] += f;
            return;
        }
        if(asum[i] == 0.f){     /* if empty slot store f */
            asum[i] = f;
            return;
        }
        f += asum[i];           /* else add slot to f, clear slot */
        asum[i] = 0.f;          /* and continue until empty slot */
    }
}

/* return sum from array */
float returnsum(float asum[256])
{
float sum = 0.f;
size_t i;
    for(i = 0; i < 256; i++)
        sum += asum[i];
    return sum;
}

exemple de double précision:

/* clear array */
void clearsum(double asum[2048])
{
size_t i;
    for(i = 0; i < 2048; i++)
        asum[i] = 0.;
}

/* add a number into array */
void addtosum(double d, double asum[2048])
{
size_t i;
    while(1){
        /* i = exponent of d */
        i = ((size_t)((*(unsigned long long *)&d)>>52))&0x7ff;
        if(i == 0x7ff){         /* max exponent, could be overflow */
            asum[i] += d;
            return;
        }
        if(asum[i] == 0.){      /* if empty slot store d */
            asum[i] = d;
            return;
        }
        d += asum[i];           /* else add slot to d, clear slot */
        asum[i] = 0.;           /* and continue until empty slot */
    }
}

/* return sum from array */
double returnsum(double asum[2048])
{
double sum = 0.;
size_t i;
    for(i = 0; i < 2048; i++)
        sum += asum[i];
    return sum;
}
rcgldr
la source
Cela ressemble un peu à la méthode de Malcolm 1971 ou, plus encore, à sa variante qui utilise l'exposant de Demmel et Hida ("Algorithme 3"). Il existe un autre algorithme qui fait une boucle basée sur le report comme le vôtre, mais je ne le trouve pas pour le moment.
ZachB
@ZachB - le concept est similaire au tri par fusion de bas en haut pour les listes liées , qui utilise également un petit tableau, où le tableau [i] pointe vers une liste avec 2 ^ i nœuds. Je ne sais pas jusqu'où cela remonte. Dans mon cas, c'était la découverte de soi dans les années 1970.
rcgldr
-1

Vos flotteurs doivent être ajoutés en double précision. Cela vous donnera plus de précision que n'importe quelle autre technique. Pour un peu plus de précision et beaucoup plus de vitesse, vous pouvez créer par exemple quatre sommes et les additionner à la fin.

Si vous ajoutez des nombres à double précision, utilisez long double pour la somme - cependant, cela n'aura un effet positif que dans les implémentations où long double a en fait plus de précision que double (généralement x86, PowerPC selon les paramètres du compilateur).

gnasher729
la source
1
«Cela vous donnera plus de précision que n'importe quelle autre technique.» Vous rendez-vous compte que votre réponse vient plus d'un an après une réponse tardive antérieure décrivant comment utiliser la sommation exacte?
Pascal Cuoq
Le type "long double" est horrible et vous ne devriez pas l'utiliser.
Jeff
-1

En ce qui concerne le tri, il me semble que si vous prévoyez une annulation, les chiffres doivent être ajoutés par ordre de grandeur décroissant et non par ordre croissant. Par exemple:

((-1 + 1) + 1e-20) donnera 1e-20

mais

((1e-20 + 1) - 1) donnera 0

Dans la première équation, deux grands nombres sont annulés, tandis que dans la seconde, le terme 1e-20 est perdu lorsqu'il est ajouté à 1, car il n'y a pas assez de précision pour le conserver.

En outre, la sommation par paires est assez décente pour additionner beaucoup de nombres.

KOAD
la source