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);
v
est 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.
c++
floating-point
precision
Yippie-Ki-Yay
la source
la source
Réponses:
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 est1 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.
la source
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,
la source
sum
etc
de grandeur différente. Il peut être étendu de manière triviale à N variables.-ffast-math
sur GCC).-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-math
mais 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-math
est raisonnable à utiliser. Par conséquent, je voudrais modifier mon commentaire «interdit» fortement formulé.sum, c, t, y
aidera. Vous devez également ajoutersum -= c
à avantreturn sum
.J'ai essayé l'exemple extrême de la réponse fournie par Steve Jessop.
J'ai obtenu le résultat suivant:
L'erreur dans la première ligne est plus de dix fois plus grande dans la seconde.
Si je change le
double
s enfloat
s dans le code ci-dessus, j'obtiens: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
double
s) comme décrit par Daniel Pryden:J'obtiens exactement 2.0:
Et même si je change le
double
s enfloat
s dans le code ci-dessus, j'obtiens:Il semblerait que Kahan soit la voie à suivre!
la source
double
cela ne souffre pas mal perte de précision en additionnant un milliard de milliardièmes, puisqu'il a 52 bits significatifs, alors que l'IEEEfloat
n'en a que 24 et le ferait.c
pour 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'double
arithmétique.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:
Source: Algorithme 908: Somme exacte en ligne des flux à virgule flottante .
la source
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:
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.
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
la source
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:
Bien sûr, cet algorithme sera plus efficace avec une file d'attente prioritaire au lieu d'une liste. Code C ++:
chauffeur:
Les nombres dans la file d'attente sont négatifs car
top
donne 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.la source
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.
la source
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 ++.
la source
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:
exemple de double précision:
la source
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).
la source
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.
la source