Quelles sont les causes des erreurs darrondi en virgule flottante?

Ceci est dû au fait que certaines fractions ont besoin dune quantité très grande (voire infinie) de places pour être exprimées sans arrondi. Cela est vrai pour la notation décimale autant que pour le binaire ou tout autre. Si vous limitez le nombre de décimales à utiliser pour vos calculs (et évitez de faire des calculs en notation fractionnaire), vous devrez arrondir même une expression simple à 1/3 + 1/3. Au lieu décrire 2/3 en conséquence, vous devriez écrire 0,33333 + 0,33333 = 0,666666 qui nest pas identique à 2/3.

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

Ce que tout informaticien doit savoir sur larithmétique à virgule flottante

Commentaires

• Spot on. Mais je voudrais également noter que certains nombres se terminent en décimal don ‘ t se terminent en binaire. En particulier, 0,1 est un nombre récurrent en binaire et donc aucun nombre binaire à virgule flottante ne peut représenter exactement 0,1.
• Flottant les points ne sont ‘ que utiles pour un grand nombre de décimales. Les entiers 32 bits ne peuvent compter que jusquà environ 4 milliards, mais un flottant 32 bits peut être presque infiniment grand.
• En particulier, les fractions que nous pouvons exprimer en décimales finies sont celles dont les dénominateurs ‘ factorisation premiers ne contiennent que 2 et 5 (par exemple, nous pouvons exprimer 3/10 et 7/25 , mais non 11/18). Lorsque nous passons au binaire, nous perdons le facteur 5, de sorte que seuls les rationnels dyadiques (par exemple 1/4, 3/128) peuvent être exprimés exactement.

Principalement, les erreurs darrondi viennent du fait que linfini de tous les nombres réels ne peut pas être représenté par la mémoire finie d’un ordinateur , sans parler d’une petite tranche de mémoire telle qu’une seule variable à virgule flottante , tant de nombres stockés ne sont que approximations du nombre quelles sont censées représenter.

Puisquil ny a quun nombre limité de valeurs qui sont et non une approximation, et toute opération entre une approximation et un autre nombre aboutit à une approximation, les erreurs darrondi sont presque inévitables .

Limportant la chose est de réaliser quand ils sont susceptibles de causer un problème et prendre des mesures pour atténuer les risques .

En plus de David Goldberg « s essentiel What Every Computer Scientis t Should Know About Floating-Point Arithmetic (republié par Sun / Oracle en annexe à leur Numerical Guide de calcul ), qui a été mentionné par thorsten , le ACCU journal Surcharge a publié une excellente série darticles de Richard Harris sur Floating Point Blues .

La série a commencé par

• Vous allez devoir réfléchir! dans Surcharge n ° 99 ( pdf , p5-10):

Co numérique mputing comporte de nombreux pièges. Richard Harris commence à chercher une solution miracle.

Le dragon de lerreur numérique nest pas souvent réveillé de son sommeil, mais sil est approché avec précaution, il infligera parfois des dommages catastrophiques aux calculs du programmeur imprudent.

À tel point que certains programmeurs, layant rencontré par hasard dans les forêts darithmétique à virgule flottante IEEE 754, déconseillent à leurs camarades de voyager dans ce beau pays.

Dans cette série darticles, nous allons explorer le monde de l’informatique numérique, opposant l’arithmétique à virgule flottante à certaines des techniques qui ont été proposées comme des substituts plus sûrs. Nous apprendrons que le territoire du dragon a une portée considérable et qu’en général nous devons faire attention si nous craignons son une attention dévastatrice.

Richard commence par expliquer la taxonomie des nombres réels, rationnels, irrationnels, algébriques et transcendantaux. Il poursuit ensuite en expliquant la représentation IEEE754, avant de passer à lerreur dannulation et aux problèmes dordre dexécution.

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

Si vous voulez en savoir plus, il continue avec

• Pourquoi la virgule fixe ne guérit pas vos bleus à virgule flottante in Surcharge n ° 100 ( pdf , p15-22)
• Pourquoi Rationals ne le fera pas Soignez vos bleus à virgule flottante dans Surcharge n ° 101 ( pdf , p9-13)
• Pourquoi lalgèbre informatique ne guérit pas vos bleus à virgule flottante in Overload # 102 ( pdf , p9- 14).
• Pourquoi larithmétique dintervalle ne guérira pas vos bleus à virgule flottante dans Surcharge 103 ( pdf , p19-24)

Il passe ensuite à essayer de vous aider à guérir votre Calculus Blues

• Pourquoi [Insérer lalgorithme ici] ne guérira pas vos bleus de calcul dans Surcharge 104 ( pdf , p22-24).
• Pourquoi les différences finies ne guérissent pas vos bleus de calcul dans Surcharge 105 ( pdf , p5-12).
• Pourquoi l’approximation polynomiale a gagné « t Cure Your Calculus Blues dans Surcharge 106 ( pdf , p16-25).
• Pourquoi lalgèbre informatique ne guérira pas vos bleus de calcul in Surcharge 107 ( pdf , p15-20).

et last but not least, il y a

• Pourquoi la différenciation automatique ne guérira pas vos bleus de calcul dans Surcharge 108 ( pdf , p4-11).

Toute la série darticles est qui valent la peine dêtre examinées, et avec 66 pages au total, elles sont encore plus petites que les 77 pages du article de Goldberg .

Bien que cela la série couvre une grande partie du même terrain, je lai trouvé plus accessible que le papier de Goldberg. Jai également trouvé plus facile de comprendre les parties les plus complexes de larticle après avoir lu les premiers articles de Richards et après ces premiers articles, Richard bifurque dans de nombreux domaines intéressants non abordés par larticle de Goldberg.

Comme donc parlé ak mentionné dans les commentaires:

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

Commentaires

• En tant quauteur de ces articles, je ‘ souhaite mentionner que jen ai créé des versions interactives sur mon blog www.thusspakeak.com en commençant par thusspakeak.com/ak/2013/06 .
• Merci @ thusspakea.k. Jai ‘ ajouté une note à ma réponse, et tho Ces éléments interactifs fonctionnent très bien.

Eh bien, thorsten a le lien définitif . Jajouterais:

Toute forme de représentation aura une erreur darrondi pour un certain nombre. Essayez dexprimer 1/3 en virgule flottante IEEE ou en décimal. Aucun des deux ne peut le faire avec précision. Cela va au-delà de la réponse à votre question, mais jai utilisé cette règle empirique avec succès:

• Stockez les valeurs saisies par lutilisateur en décimal (car il les a presque certainement saisies dans une représentation décimale – très peu dutilisateurs utilisera binaire ou hexadécimal). De cette façon, vous avez toujours la représentation exacte saisie par lutilisateur.
• Si vous devez stocker des fractions saisies par lutilisateur, 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 lutilisateur peut entrer les deux, stocker la valeur quils ont entrée et les unités dans lesquelles ils les ont entrées. Nessayez pas de convertir et denregistrer en une seule représentation, à moins que vous ne puissiez le faire sans perte de précision / précision. Utilisez les unités de valeur stockées et dans tous les calculs.
• Stockez les valeurs générées par la machine en virgule flottante IEEE (il peut sagir de nombres générés par un appareil de mesure électronique, comme un capteur analogique avec un convertisseur A / N, ou le résultat non arrondi dun calcul). Notez que cela ne sapplique pas si vous lisez un capteur via une connexion série et quil donne déjà vous la valeur dans un format décimal (par exemple 18,2 C).
• Stockez les totaux visibles par lutilisateur, etc., en décimal (comme un compte bancaire équilibre). Arrondissez correctement, mais utilisez cette valeur comme valeur définitive pour tous les calculs futurs.

Commentaires

• Jajouterais: Pensez à utiliser un Un package mathématique de précision arbitraire comme ARPREC ou decNumber.
• Je ne ‘ t decimal (par opposition à binary) a beaucoup davantages pour les valeurs entières, comme le numérateur et dénominateur dune fraction. Les deux peuvent stocker des valeurs entières exactes, et le binaire est plus efficace. Il y a ‘ un coût de conversion entre les entrées et les sorties, mais ce ‘ est susceptible d’être submergé par le coût de effectuer les E / S.

Ce qui semble ne pas avoir été mentionné jusquà présent, ce sont les concepts dun algorithme instable et un problème mal conditionné . Jaborderai le premier en premier, car cela semble être un écueil plus fréquent pour les numériciens novices.

Considérons le calcul des puissances du nombre dor (réciproque) φ=0.61803…; une façon possible de procéder consiste à utiliser la formule de récurrence φ^n=φ^(n-2)-φ^(n-1), en commençant par φ^0=1 et φ^1=φ. Si vous exécutez cette récursion dans votre environnement informatique préféré 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 présumé pour φ^41 a le mauvais signe, et même avant, les valeurs calculées et réelles pour φ^39 ne partagent aucun chiffre en commun (3.484899258054952 * ^ – 9 for the computed version against the true value 7.071019424062048 *^-9). Lalgorithme est donc instable et il ne faut pas utiliser cette formule de récursivité en arithmétique inexacte. Cela est dû à la nature inhérente de la formule de récursivité: il y a une solution «décroissante» et «croissante» à cette récursivité, et essayer de calculer la solution «décroissante» par une solution en avant quand il y a une solution alternative «croissante» demande un chagrin numérique. Il faut donc sassurer que ses algorithmes numériques sont stables.

Passons maintenant au concept de problème mal conditionné : même sil peut y avoir une manière stable de faire quelque chose numériquement, il se peut très bien que le problème que vous Vous ne pouvez tout simplement pas être résolu par votre algorithme. Cest la faute du problème lui-même et non de la méthode de résolution. Lexemple canonique en numérique est la solution déquations linéaires impliquant la soi-disant « matrice de Hilbert »:

La matrice est lexemple canonique dune matrice mal conditionnée : essayer de résoudre un système avec une grande matrice de Hilbert peut renvoyer une solution inexacte.

Ici « sa Mathematica démonstration: comparez les résultats de larithmé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 de larithmé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 lavez essayé dans Mathematica , vous noterez quelques messages derreur avertissant de lapparition dun mauvais conditionnement.)

Dans les deux cas, il suffit daugmenter le la précision nest pas un remède; cela ne fera que retarder linévitable érosion des figures.

Cest ce à quoi vous pourriez être confronté. Les solutions peuvent être difficiles: pour la première, soit vous retournez à la planche à dessin, soit vous parcourez des journaux / livres / quoi que ce soit pour trouver si quelquun dautre a trouvé une meilleure solution que vous; pour la seconde, soit vous abandonnez, soit vous reformulez votre problème en quelque chose de plus traitable.

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

La vie peut nous poser des problèmes mal conditionnés, mais il ny a aucune bonne raison de se contenter dun algorithme instable.

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

ou en dautres termes 1/10 ne peut pas être transformée en une fraction avec une puissance de 2 dans le dénominateur (ce que sont essentiellement les nombres à virgule flottante)

Commentaires

• Pas exactement vrai: 0,5 et 0,25 peut être exprimé en base 2. Je pense que vous voulez dire  » pas tous les nombres décimaux de base 10 « .
• Plus précisément. Tous les nombres fractionnaires ne peuvent pas être représentés exactement en utilisant une notation à virgule flottante (cest-à-dire avec le. Base 2 et base 10 ont ce problème exact). Essayez et faites 9*3.3333333 en décimal et comparez-le à 9*3 1/3
• Cest la source la plus courante de virgule flottante confusion. .1 + .1 != .2 car le codage binaire à virgule flottante est utilisé, pas décimal.
• @SeanMcMillan: Et 1.0/3.0*3.0 != 1.0, car flottant un encodage binaire en points est utilisé, pas trinaire.

En mathématiques, il y a une infinité de nombres rationnels . Une variable 32 bits ne peut avoir que 2 ³² valeurs différentes et une variable 64 bits uniquement 2 valeurs ⁶⁴ . Par conséquent, il existe une infinité de nombres rationnels qui nont pas de représentation précise.

Nous pourrions proposer des schémas qui nous permettraient de représenter parfaitement 1/3, ou 1/100. Il savère que pour de nombreuses raisons pratiques, ce nest pas très utile. Il y a une grande exception: en finance, les fractions décimales apparaissent souvent. Cest principalement parce que la finance est essentiellement une activité humaine et non physique.

Par conséquent, nous choisissons généralement dutiliser une virgule flottante binaire et darrondir 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. .

Commentaires

• Pire encore, alors quune quantité infinie (dénombrable infinie) de mémoire permettrait de représenter tous les rationnels, elle ne le ferait pas suffit 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 est dapproximer un sous-ensemble fini de réels.
• @Kevin: Vous ‘ parlez des nombres calculables, qui est un petit sous-ensemble (un sous-ensemble avec une mesure zéro) des réels.
• +1 pour le explication la plus élémentaire: vous ‘ essayez de représenter une quantité infinie de nombres avec un nombre fini de bits.
• @DavidHammen: Les nombres calculables sont un petit sous-ensemble ( de mesure zéro) des réels – mais chaque nombre avec lequel vous ‘ travaillez dans un programme est, par définition, calculable.
• @Giorgio: Si vous choisissez la bonne représentation, la racine carrée de 2 est représentable, par exemple, comme la chaîne "√2". (Mon ancienne calculatrice HP-48 était capable de faire exactement cela, et la mise au carré de cette valeur donnait exactement 2.0.) Il ny a quune infinité dénombrable de nombres réels représentables pour tout représentation finie – mais aucun calcul ne peut donner un nombre qui nest en principe pas représentable. En pratique, la virgule flottante binaire limite considérablement lensemble des nombres représentables, avec lavantage dune vitesse fulgurante et dun stockage minime par rapport aux représentations symboliques.

Le seul « problème darrondi » vraiment évident avec les nombres à virgule flottante auquel je pense est celui des 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 laccumulation 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] $ que vous soustrayerez $ N $ échantillons dans le futur. si ce nest pas le cas, ce qui est différent, cest un petit étron qui reste coincé dans votre ligne à retard et qui ne sortira jamais. cest parce que ce filtre de moyenne mobile est en fait construit avec un IIR qui a un pôle marginalement stable à $ z = 1 $ et un zéro qui lannule à lintérieur. mais, cest un intégrateur et toute merde qui est intégrée et non entièrement supprimée existera pour toujours dans la somme de lintégrateur. Cest là que la virgule fixe na pas le même problème que les nombres à virgule flottante.

Commentaires

• hey, doesn ‘ t $ LaTeX $ math markup fonctionne dans le forum prog.SE ??? que ‘ est vraiment nul si ce nest pas le cas ‘ t.
• Voir ceci sur meta.SO et questions liées