Votre instinct est fondamentalement de droite, dans l'ordre croissant (de grandeur) améliore quelque peu les choses. Considérons le cas où nous sommes en ajoutant simple précision (32 bits) flotte, et il y a 1 milliards de dollars des valeurs égales à 1 / (1 milliard), et une valeur égale à 1. Si le 1 est premier, alors la somme viendra à 1, puisque 1 + (1 / 1 milliards de dollars) est de 1 à cause de la perte de précision. Chaque addition n'a aucun effet sur le total.
Si les petites valeurs de venir en premier, ils auront au moins la somme à quelque chose, mais même alors, j'ai 2^30 d'entre eux, alors qu'après 2^25 ou alors je suis de retour dans la situation où chacun, individuellement, n'est-ce pas touchant au total plus de. Donc, je vais encore avoir besoin de plus d'astuces.
C'est un cas extrême, mais en général, l'ajout de deux valeurs du même ordre de grandeur est plus précise que l'ajout de deux valeurs très différentes grandeurs, puisque vous "jeter" moins de bits de précision dans la plus petite valeur de cette façon. En triant les chiffres, vous les valeurs du groupe du même ordre de grandeur ensemble, et en les ajoutant dans l'ordre croissant vous donner les petites valeurs une "chance" de façon cumulative d'atteindre la grandeur du plus grand nombre.
Encore, si les nombres négatifs sont impliqués, il est facile de "berner" cette approche. Considérons trois valeurs à additionner, {1, -1, 1 billionth}. L'arithmétique correcte somme est 1 billionth, mais si mon premier ajout implique la minuscule de la valeur, puis mon somme finale sera de 0. Du 6 ordres possibles, seulement 2 sont "correctes" - {1, -1, 1 billionth} et {-1, 1, 1 billionth}. Tous les 6 ordres de donner des résultats précis à l'échelle de la plus grande amplitude de valeur dans l'entrée (0.0000001%), mais pour 4 d'entre elles, le résultat est inexacte à l'échelle de la solution réelle (100%). Le problème que vous résolvez vous dira si le premier est assez bon ou pas.
En fait, vous pouvez jouer beaucoup plus de trucs que simplement en ajoutant dans l'ordre de tri. Si vous avez beaucoup de très petites valeurs, un nombre moyen de médiocre, les valeurs, et un petit nombre de grandes valeurs, alors il peut être plus précis pour ajouter tous les petits, puis, séparément, le total de la médiocre, ajouter ces deux totaux ensemble, puis ajouter les grands. Il n'est pas trivial de trouver la plus précise de la combinaison de virgule flottante ajouts, mais de composer avec vraiment mauvais cas, vous pouvez conserver l'ensemble des totaux en cours d'exécution à différentes amplitudes, ajouter chaque nouvelle valeur pour le total qui correspond le mieux à son ampleur, et lors de l'exécution d'un total commence à être trop grand pour sa grandeur, l'ajouter dans la prochaine total et en commencer une nouvelle. Poussé à son extrême logique, ce processus est équivalent à l'exécution de la somme dans une précision arbitraire type (donc, si vous voulez le faire). Mais compte tenu de l'simpliste choix d'ajouter dans l'ordre croissant ou décroissant de grandeur, l'ascension, c'est le meilleur pari.
Il n'en relation avec le monde réel de la programmation, car il y a certains cas où votre calcul peut aller très mauvais si vous avez accidentellement couper un "lourd" queue composé d'un grand nombre de valeurs de chaque de ce qui est trop petit, individuellement, d'affecter le montant, ou si vous jetez trop de précision à partir d'un grand nombre de petites valeurs qui, individuellement, n'affectent que la dernière quelques bits de la somme. Dans les cas où la queue est négligeable, de toute façon vous n'avez probablement pas de soins. Par exemple, si vous êtes seulement l'addition d'un petit nombre de valeurs, en premier lieu, et vous êtes seulement à l'aide de quelques chiffres significatifs de la somme.
