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

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?

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

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

• Vous allez devoir penser! ensurcharge n ° 99( pdf , p5-10):

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

• Pourquoi le virgule fixe ne guérit pas votre blues àvirgule flottante ensurcharge # 100( pdf , p15-22)
• Pourquoi Rationals ne guérira- t-il pas votre blues envirgule flottante ensurcharge # 101( pdf , p9-13)
• Pourquoi l’algèbre informatique ne guérira-t-elle pas votre blues àvirgule flottante ensurcharge # 102( pdf , p9-14).
• Pourquoi l'arithmétique par intervalles ne résout pas le problème du blues envirgule flottante ensurcharge 103( pdf , p19-24)

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

• Pourquoi [Insérer l'algorithme ici] ne résoudra pas vos problèmes de calcul ensurcharge 104( pdf , p22-24).
• Pourquoi des différences finies ne résoudront pas le problème du calcul ensurcharge 105( pdf , p5-12).
• Pourquoi l'approximation polynomiale ne résout pas le problème du calcul ensurcharge 106( pdf , p16-25).
• Pourquoi l'algèbre informatique ne résout pas le problème du calcul ensurcharge 107( pdf , p15-20).

et le dernier mais non le moindre, il y a

• Pourquoi la différenciation automatique ne résout pas le problème du calcul ensurcharge 108( pdf , p4-11).

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 .

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.

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":

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.

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)

En mathématiques, il y a une infinité de nombres rationnels. Une variable de 32 bits ne peut avoir que 2 ³² valeurs différentes et une variable de 64 bits, seulement 2 ⁶⁴ 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.

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.