Qu'est-ce qui cause les erreurs d'arrondi en virgule flottante?

62

Je suis conscient que l'arithmétique en virgule flottante pose des problèmes de précision. Je les surmonte généralement en basculant vers une représentation décimale fixe du nombre ou simplement en négligeant l'erreur.

Cependant, je ne sais pas quelles sont les causes de cette inexactitude. Pourquoi y a-t-il tant de problèmes d'arrondi avec les nombres flottants?

nmat
la source
28
Pour être précis, la plupart des gens ne s'inquiètent pas de l' erreur liée à l'arrondissement, mais plutôt du fait que l'arrondissement binaire en virgule flottante se comporte de manière peu intuitive. Le passage à une représentation décimale peut faire l'arrondi se comportent d'une manière plus intuitive, mais en échange vous presque toujours augmenter l'erreur relative (ou bien avoir à augmenter l'espace de stockage pour compenser).
Daniel Pryden
12
Ma tentative d'éclaircir les confusions les plus courantes: floating-point-gui.de
Michael Borgwardt
Je pense que @DanielPryden signifie "Le passage à une représentation [à virgule fixe] peut rendre l'arrondi se comporter de manière plus intuitive ..." . ce qui cause des problèmes d’arrondi, qu’il s’agisse de nombres fixes ou à virgule flottante, c’est la largeur de mot fini de l’un ou l’autre. c'est simplement qu'en virgule flottante, l'amplitude de l'erreur d'arrondi reste normalement à peu près proportionnelle à celle du nombre arrondi. (sauf quand vous êtes vraiment petit et que vous avez des nombres "dénormalisés".)
robert bristow-johnson
@ Robert: Ce n'est pas exactement ce que je faisais référence. L '"erreur" que la plupart des gens rencontrent avec une virgule flottante n'a rien à voir avec une virgule flottante en soi, c'est la base. Les flotteurs et les doubles IEEE-754 utilisent un exposant en base 2, ce qui signifie que les nombres fractionnaires sont arrondis à des puissances négatives de deux (1/2, 1/16, 1/1024, etc.) plutôt qu'à des puissances négatives de 10 (1 / 10, 1/1000, etc.) Ceci conduit à des résultats non intuitifs tels que 0,1 arrondi à 0.1000001 et des problèmes similaires.
Daniel Pryden
Vous pouvez créer des nombres à virgule flottante en base 10 - c'est ainsi que fonctionne le decimaltype .NET . Le point fixe, en revanche, est différent. Tant que votre portée est limitée, le point fixe est une bonne réponse. Cependant, la plage restrictive rend le point fixe inutilisable pour de nombreuses applications mathématiques, et les implémentations de nombres à virgule fixe ne sont souvent pas bien optimisées matériellement.
Daniel Pryden

Réponses:

82

En effet, certaines fractions ont besoin d'un très grand nombre (voire d'infinies) de points à exprimer sans arrondis. Cela est vrai autant pour la notation décimale que pour la notation binaire ou autre. Si vous souhaitez limiter le nombre de décimales à utiliser pour vos calculs (et éviter de faire des calculs en notation décimale), vous devrez arrondir même une expression simple sous la forme 1/3 + 1/3. Au lieu d'écrire 2/3, vous devrez écrire 0.33333 + 0.33333 = 0.66666, ce qui n'est pas identique à 2/3.

Dans le cas d’un ordinateur, le nombre de chiffres est limité par la nature technique de la mémoire et des registres de la CPU. La notation binaire utilisée en interne ajoute quelques difficultés supplémentaires. Les ordinateurs ne peuvent normalement pas exprimer les nombres avec des fractions, bien que certains langages de programmation ajoutent cette possibilité, ce qui permet d’éviter ces problèmes dans une certaine mesure.

Ce que tout informaticien devrait savoir sur l'arithmétique en virgule flottante

Thorsten Müller
la source
12
Spot sur. Mais je voudrais aussi noter que certains nombres qui se terminent en décimal ne se terminent pas en binaire. En particulier 0,1 est un nombre récurrent en binaire et aucun nombre binaire à virgule flottante ne peut donc représenter exactement 0,1.
Jack Aidley
4
Les points flottants ne sont pas seulement utiles pour beaucoup de décimales. Les entiers 32 bits ne peuvent compter que 4 milliards environ, mais un nombre flottant 32 bits peut être presque infiniment grand.
Abhi Beckert
7
En particulier, les fractions que nous pouvons exprimer en nombres décimaux finis sont celles dont la factorisation première des dénominateurs ne contient que 2 et 5 (par exemple, nous pouvons exprimer 3/10 et 7/25, mais pas 11/18). Lorsque nous passons au mode binaire, nous perdons le facteur 5, de sorte que seuls les rationnels dyadiques (par exemple 1/4, 3/128) peuvent être exprimés avec exactitude.
David Zhang
70

Les erreurs d'arrondi proviennent principalement du fait que l' infini de tous les nombres réels ne peut pas être représenté par la mémoire finie d'un ordinateur , sans parler d'une minuscule tranche de mémoire telle qu'une variable à virgule flottante unique , de sorte qu'un grand nombre de nombres stockés ne sont que des approximations le nombre qu'ils sont censés représenter.

Etant donné qu’il n’ya qu’un nombre limité de valeurs qui ne sont pas approximatives et que toute opération entre une approximation et un autre nombre donne une approximation, les erreurs d’arrondi sont presque inévitables .

L'important est de savoir quand ils risquent de causer un problème et de prendre des mesures pour atténuer les risques .


En plus de David Goldberg essentiel de ce que chaque informaticien devrait savoir sur Arithmétique flottante (réédité par Sun / Oracle en annexe à leur guide numérique de calcul ), qui a été mentionné par thorsten , la ACCU revue de surcharge a couru un excellent série d'articles de Richard Harris sur le Floating Point Blues .

La série a commencé avec

L'informatique numérique comporte de nombreux pièges. Richard Harris commence à chercher une solution miracle.

Le dragon de l'erreur numérique n'est pas souvent réveillé de son sommeil, mais s'il est approché avec imprudence, il infligera de temps en temps des dégâts catastrophiques aux calculs du programmeur imprudent.

À tel point que certains programmeurs, après l'avoir découvert par hasard dans les forêts d'arithmétique à virgule flottante IEEE 754, déconseillent à leurs compagnons de voyager dans ce beau pays.

Dans cette série d'articles, nous explorerons le monde de l'informatique numérique en opposant l'arithmétique en virgule flottante à certaines des techniques qui ont été proposées pour le remplacer de manière plus sûre. Nous apprendrons que le territoire du dragon est vraiment vaste et qu'en général nous devons agir avec prudence si nous craignons son attention dévastatrice.

Richard commence par expliquer la taxonomie des nombres réels, rationnelle, irrationnelle, algébrique et transcendantale. Il explique ensuite la représentation IEEE754 avant de passer à l’erreur d’annulation et aux problèmes d’ordre d’exécution.

Si vous ne lisez pas plus profondément que cela, vous aurez une excellente base sur les problèmes associés aux nombres en virgule flottante.

Si vous voulez en savoir plus cependant, il continue avec

Il passe ensuite à essayer de vous aider à guérir vos calculs bleus

et le dernier mais non le moindre, il y a

Toute la série d'articles mérite d'être examinée et, avec un total de 66 pages, ils sont toujours plus petits que les 77 pages du document Goldberg .

Bien que cette série couvre à peu près le même terrain, je l’ai trouvée un peu plus accessible que le papier de Goldberg . J'ai également trouvé plus facile de comprendre les parties les plus complexes du document après avoir lu les premiers articles de Richards et, après ces premiers articles, Richard a commencé par explorer de nombreux domaines intéressants non abordés dans le document de Goldberg.


Comme dit ainsi ak mentionné dans les commentaires:

En tant qu'auteur de ces articles, je voudrais mentionner que j'en ai créé des versions interactives sur mon blog www.thusspakeak.com en commençant par thusspakeak.com/ak/2013/06 .

Mark Booth
la source
1
En tant qu'auteur de ces articles, je voudrais mentionner que j'en ai créé des versions interactives sur mon blog www.thusspakeak.com en commençant par thusspakeak.com/ak/2013/06 .
Ainsi parla
Merci à thusspakea.k. J'ai ajouté une note à ma réponse et ces éléments interactifs fonctionnent très bien.
Mark Booth le
12

Eh bien, Thorsten a le lien définitif . J'ajouterais:

Toute forme de représentation comportera une erreur d’arrondi pour un certain nombre. Essayez d’exprimer 1/3 en virgule flottante IEEE ou en décimal. Ni peut le faire avec précision. Cela va au-delà de répondre à votre question, mais j'ai utilisé cette règle de base avec succès:

  • Stockez les valeurs saisies par les utilisateurs en décimal (car ils les ont certainement saisies sous forme de représentation décimale - très peu d’utilisateurs utiliseront binaire ou hexadécimal). De cette façon, vous avez toujours la représentation exacte saisie par l'utilisateur.
  • Si vous devez stocker des fractions entrées par l'utilisateur, stockez le numérateur et le dénominateur (également en décimal)
  • Si vous avez un système avec plusieurs unités de mesure pour la même quantité (comme Celsius / Fahrenheit) et que l'utilisateur peut entrer les deux, enregistre la valeur saisie et les unités dans lesquelles il les a entrées. N'essayez pas de convertir et d'enregistrer sous une seule représentation, à moins que vous ne puissiez le faire sans perte de précision / exactitude. Utilisez la valeur et les unités stockées dans tous les calculs.
  • Stockez les valeurs générées par la machine en virgule flottante IEEE (il peut s'agir de nombres générés par un dispositif de mesure électronique, comme un capteur analogique avec un convertisseur A / N, ou du résultat non arrondi d'un calcul). Notez que cela ne s'applique pas si vous lisez un capteur sur une connexion série et que cela vous donne déjà la valeur au format décimal (par exemple 18.2 C).
  • Stockez les totaux visualisables par l'utilisateur, etc., en décimal (comme un solde de compte bancaire). Arrondissez de manière appropriée, mais utilisez cette valeur comme valeur définitive pour tous les calculs futurs.
Scott Whitlock
la source
J'ajouterais: Pensez à utiliser un progiciel mathématique de précision arbitraire comme ARPREC ou decNumber.
Blrfl
Je ne décimal (par opposition à binaire) a beaucoup d'avantages pour les valeurs entières, telles que le numérateur et le dénominateur d'une fraction. Les deux peuvent stocker des valeurs entières exactes et binaire est plus efficace. Il y a des coûts de conversion aller-retour pour les entrées et les sorties, mais le coût de la réalisation physique des E / S sera probablement submergé.
Keith Thompson
10

Ce qui semble ne pas avoir été mentionné jusqu'ici, ce sont les concepts d'un algorithme instable et d'un problème mal conditionné . Je vais aborder le premier en premier, car cela semble être un écueil plus fréquent pour les numericists novices.

Considérons le calcul des puissances du nombre d'or (réciproque) φ=0.61803…; Une solution possible consiste à utiliser la formule de récurrence φ^n=φ^(n-2)-φ^(n-1), en commençant par φ^0=1et φ^1=φ. Si vous exécutez cette récursivité dans votre environnement informatique favori et comparez les résultats avec des puissances évaluées avec précision, vous constaterez une lente érosion des chiffres significatifs. Voici ce qui se passe par exemple dans Mathematica :

ph = N[1/GoldenRatio];  
Nest[Append[#1, #1[[-2]] - #1[[-1]]] & , {1, ph}, 50] - ph^Range[0, 51]  
{0., 0., 1.1102230246251565*^-16, -5.551115123125783*^-17, 2.220446049250313*^-16, 
-2.3592239273284576*^-16, 4.85722573273506*^-16, -7.147060721024445*^-16, 
1.2073675392798577*^-15, -1.916869440954372*^-15, 3.1259717037102064*^-15, 
-5.0411064211886014*^-15, 8.16837916750579*^-15, -1.3209051907825398*^-14, 
2.1377864756200182*^-14, -3.458669982359108*^-14, 5.596472721011714*^-14, 
-9.055131861349097*^-14, 1.465160458236081*^-13, -2.370673237795176*^-13, 
3.835834102607072*^-13, -6.206507137114341*^-13, 1.004234127360273*^-12, 
-1.6248848342954435*^-12, 2.6291189633497825*^-12, -4.254003796798193*^-12, 
6.883122762265558*^-12, -1.1137126558640235*^-11, 1.8020249321541067*^-11, 
-2.9157375879969544*^-11, 4.717762520172237*^-11, -7.633500108148015*^-11, 
1.23512626283229*^-10, -1.9984762736468268*^-10, 3.233602536479646*^-10, 
-5.232078810126407*^-10, 8.465681346606119*^-10, -1.3697760156732426*^-9, 
2.216344150333856*^-9, -3.5861201660070964*^-9, 5.802464316340953*^-9, 
-9.388584482348049*^-9, 1.5191048798689004*^-8, -2.457963328103705*^-8, 
3.9770682079726053*^-8, -6.43503153607631*^-8, 1.0412099744048916*^-7, 
-1.6847131280125227*^-7, 2.725923102417414*^-7, -4.4106362304299367*^-7, 
7.136559332847351*^-7, -1.1547195563277288*^-6}

Le résultat supposé pour φ^41a le mauvais signe et, même avant, les valeurs calculées et réelles pour le φ^39partage sans chiffres en commun ( 3.484899258054952* ^ - 9 for the computed version against the true value7.071019424062048 *^-9). L'algorithme est donc instable, et il ne faut pas utiliser cette formule de récurrence en arithmétique inexacte. Cela est dû à la nature inhérente de la formule de récursivité: il existe une solution "décroissante" et "croissante" à cette récursion, et essayer de calculer la solution "décroissante" par solution en aval lorsqu'il existe une solution alternative "croissante" pour le deuil numérique. Il faut donc s’assurer que ses algorithmes numériques sont stables.

Passons maintenant au concept de problème mal conditionné : même s’il peut exister un moyen stable de faire quelque chose de manière numérique, il se peut très bien que le problème que vous avez ne puisse pas être résolu par votre algorithme. C'est la faute du problème lui-même et non la méthode de la solution. L'exemple canonique en numérique est la solution d'équations linéaires impliquant la "matrice de Hilbert":

Matrice de Hilbert

La matrice est l'exemple canonique d'une matrice mal conditionnée : essayer de résoudre un système avec une grande matrice de Hilbert pourrait donner une solution inexacte.

Voici une démonstration de Mathematica : comparez les résultats de l'arithmétique exacte

Table[LinearSolve[HilbertMatrix[n], HilbertMatrix[n].ConstantArray[1, n]], {n, 2, 12}]
{{1, 1}, {1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 
  1}, {1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1,
   1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 
  1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}}

et arithmétique inexacte

Table[LinearSolve[N[HilbertMatrix[n]], N[HilbertMatrix[n].ConstantArray[1, n]]], {n, 2, 12}]
{{1., 1.}, {1., 1., 1.}, {1., 1., 1., 1.}, {1., 1., 1., 1., 1.},  
  {1., 1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1., 1.}, 
  {1., 1., 1., 1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1., 1., 1., 1.},  
  {1., 1., 1., 0.99997, 1.00014, 0.999618, 1.00062, 0.9994, 1.00031, 
  0.999931}, {1., 1., 0.999995, 1.00006, 0.999658, 1.00122, 0.997327, 
  1.00367, 0.996932, 1.00143, 0.999717}, {1., 1., 0.999986, 1.00022, 
  0.998241, 1.00831, 0.975462, 1.0466, 0.94311, 1.04312, 0.981529, 
  1.00342}}

(Si vous l'avez essayé dans Mathematica , vous remarquerez quelques messages d'erreur indiquant que le mauvais conditionnement apparaît.)

Dans les deux cas, augmenter simplement la précision n'est pas un remède; cela ne fera que retarder l'érosion inévitable des chiffres.

C'est ce à quoi vous pourriez être confronté. Les solutions peuvent être difficiles: pour la première fois, soit vous retournez à la planche à dessin, soit vous parcourez des revues / livres / tout ce que vous voulez pour savoir si quelqu'un d'autre a proposé une meilleure solution que la vôtre; pour le second, vous abandonnez ou reformulez votre problème en quelque chose de plus simple.


Je vous laisse avec une citation de Dianne O'Leary:

La vie peut nous jeter des problèmes mal conditionnés, mais il n'y a pas de bonne raison de se contenter d'un algorithme instable.


la source
9

parce que les nombres décimaux en base 10 ne peuvent pas être exprimés en base 2

ou en d'autres termes, 1/10 ne peut pas être transformé en une fraction avec une puissance de 2 dans le dénominateur (qui sont essentiellement les nombres en virgule flottante)

monstre à cliquet
la source
11
Ce n'est pas tout à fait vrai: 0,5 et 0,25 peuvent être exprimés en base 2. Je pense que vous voulez dire "pas tous les nombres décimaux en base 10".
Scott Whitlock
3
Plus précisément. Tous les nombres fractionnaires ne peuvent pas être représentés exactement en utilisant une notation à virgule flottante (c'est-à-dire avec le. La base 2 et la base 10 ont exactement le même problème). Essayez et faites 9*3.3333333en décimal et comapre-le9*3 1/3
Martin York
1
C'est la source la plus courante de confusion en virgule flottante. .1 + .1 != .2parce que l'encodage binaire en virgule flottante est utilisé et non décimal.
Sean McMillan
@SeanMcMillan: Et 1.0/3.0*3.0 != 1.0, parce que l'encodage binaire en virgule flottante est utilisé, pas trinaire.
Keith Thompson
8

En mathématiques, il y a une infinité de nombres rationnels. Une variable de 32 bits ne peut avoir que 2 32 valeurs différentes et une variable de 64 bits, seulement 2 64 valeurs. Par conséquent, il existe une infinité de nombres rationnels sans représentation précise.

Nous pourrions proposer des solutions nous permettant de représenter parfaitement 1/3, soit 1/100. Il s'avère que pour de nombreux objectifs pratiques, cela n'est pas très utile. Il existe une grande exception: en finance, les fractions décimales apparaissent souvent. C'est principalement parce que la finance est essentiellement une activité humaine et non physique.

Par conséquent, nous choisissons généralement d'utiliser un nombre à virgule flottante binaire et arrondissons toute valeur qui ne peut pas être représentée en binaire. Mais en finance, nous choisissons parfois une virgule flottante décimale et arrondissons les valeurs à la valeur décimale la plus proche.

MSalters
la source
2
Pire encore, si une quantité infinie de mémoire permettrait de représenter tous les rationnels, elle ne suffirait pas pour représenter les réels. Pire encore, presque tous les nombres réels ne sont pas des nombres calculables. Le mieux que nous puissions faire avec une quantité finie de mémoire consiste à approximer un sous-ensemble de plages finies des réels.
David Hammen
4
@ Kevin: Vous parlez des nombres calculables, qui est un minuscule sous-ensemble (un sous-ensemble avec la mesure zéro) des réels.
David Hammen
1
+1 pour l'explication la plus élémentaire: vous essayez de représenter une quantité infinie de nombres avec un nombre fini de bits.
Raku
1
@DavidHammen: Les nombres calculables sont un minuscule sous-ensemble (de la mesure zéro) des réels - mais chaque nombre avec lequel vous travaillez dans un programme est, par définition, calculable.
Keith Thompson
3
@Giorgio: Si vous choisissez la bonne représentation, la racine carrée de 2 est représentable, par exemple, en tant que chaîne "√2". (Mon ancienne calculatrice HP-48 était capable de faire exactement cela et la quadrature de cette valeur donnait exactement cela 2.0.) Il n'y a qu'une infinité dénombrable de nombres réels représentables pour toute représentation finie - mais aucun calcul ne peut produire un nombre qui ne l'est pas. en principe, représentable. En pratique, la virgule flottante binaire limite considérablement l'ensemble des nombres représentables, avec l'avantage d'une vitesse fulgurante et d'un stockage minime par rapport aux représentations symboliques.
Keith Thompson
-2

le seul "problème d'arrondi" vraiment évident avec les nombres à virgule flottante auquel je pense est celui avec les filtres de moyenne mobile:

$$ \ begin {align} y [n] & = \ frac {1} {N} \ sum \ limits_ {i = 0} ^ {N-1} x [ni] \ & = y [n-1] + \ frac {1} {N} (x [n] - x [nN]) \ \ end {align} $$

pour que cela fonctionne sans l'accumulation de bruit, vous voulez vous assurer que le $ x [n] $ que vous ajoutez dans les échantillons actuels est exactement le même que le $ x [nN] $ vous soustrairez $ N $ échantillons dans le futur. si ce n'est pas le cas, alors ce qui est différent, c'est une petite crotte qui reste coincée dans votre ligne à retard et qui ne sortira jamais. c'est parce que ce filtre à moyenne mobile est en fait construit avec un IIR qui a un pôle marginalement stable à $ z = 1 $ et un zéro qui l'annule à l'intérieur. mais, c’est un intégrateur et toute merde intégrée et non supprimée existera toujours dans la somme des intégrateurs. C’est là que le point fixe n’a pas le même problème que les nombres à virgule flottante.

robert bristow-johnson
la source
hé, le balisage mathématique $ LaTeX $ ne fonctionne-t-il pas dans le forum prog.SE ??? c'est vraiment nul si ce n'est pas le cas.
robert bristow-johnson
1
Consultez cette question sur meta.SO et questions
connexes