Question Les mathématiques à virgule flottante sont-elles brisées


Considérez le code suivant:

0.1 + 0.2 == 0.3  ->  false
0.1 + 0.2         ->  0.30000000000000004

Pourquoi ces inexactitudes se produisent-elles?


2259
2018-02-25 21:39


origine


Réponses:


Binaire point flottant les maths sont comme ça. Dans la plupart des langages de programmation, il est basé sur Norme IEEE 754. JavaScript utilise la représentation en virgule flottante 64 bits, qui est la même que Java double. Le noeud du problème est que les nombres sont représentés dans ce format comme un nombre entier fois une puissance de deux; numéros rationnels (tels que 0.1, lequel est 1/10) dont le dénominateur n'est pas une puissance de deux ne peut être exactement représenté.

Pour 0.1 dans la norme binary64 format, la représentation peut être écrite exactement comme

  • 0.1000000000000000055511151231257827021181583404541015625 en décimal, ou
  • 0x1.999999999999ap-4 dans Notation C99 hexfloat.

En revanche, le nombre rationnel 0.1, lequel est 1/10, peut être écrit exactement comme

  • 0.1 en décimal, ou
  • 0x1.99999999999999...p-4 dans un analogue de la notation C99 hexfloat, où le ... représente une séquence sans fin de 9.

Les constantes 0.2 et 0.3 dans votre programme seront également des approximations de leurs vraies valeurs. Il arrive que le plus proche double à 0.2 est plus grand que le nombre rationnel 0.2 mais que le plus proche double à 0.3 est plus petit que le nombre rationnel 0.3. La somme de 0.1 et 0.2 finit par être plus grand que le nombre rationnel 0.3 et donc en désaccord avec la constante dans votre code.

Un traitement assez complet des problèmes arithmétiques à virgule flottante est Ce que tout informaticien devrait savoir sur l'arithmétique en virgule flottante. Pour une explication plus facile à digérer, voir floating-point-gui.de.


1718
2018-04-18 11:52



La perspective d'un concepteur de matériel

Je crois que je devrais ajouter la perspective d'un concepteur de matériel à ceci puisque je conçois et construis le matériel de virgule flottante. Connaître l'origine de l'erreur peut aider à comprendre ce qui se passe dans le logiciel et, en fin de compte, j'espère que cela aide à expliquer pourquoi les erreurs à virgule flottante se produisent et semblent s'accumuler avec le temps.

1. Vue d'ensemble

Du point de vue de l'ingénierie, la plupart des opérations en virgule flottante comportent un élément d'erreur puisque le matériel qui effectue les calculs en virgule flottante doit seulement avoir une erreur inférieure à la moitié d'une unité à la dernière place. Par conséquent, beaucoup de matériel s'arrêtera à une précision qui est seulement nécessaire pour produire une erreur de moins de la moitié d'une unité à la dernière place pour un opération unique ce qui est particulièrement problématique dans la division en virgule flottante. Ce qui constitue une seule opération dépend du nombre d'opérandes prises par l'unité. Pour la plupart, c'est deux, mais certaines unités prennent trois opérandes ou plus. Pour cette raison, il n'y a aucune garantie que des opérations répétées se traduiront par une erreur souhaitable puisque les erreurs s'additionnent avec le temps.

2. Normes

La plupart des processeurs suivent la IEEE-754 standard, mais certains utilisent denormalized, ou des normes différentes . Par exemple, il existe un mode dénormalisé dans IEEE-754 qui permet la représentation de très petits nombres à virgule flottante au détriment de la précision. Ce qui suit, cependant, couvrira le mode normalisé de IEEE-754 qui est le mode de fonctionnement typique.

Dans la norme IEEE-754, les concepteurs de matériel ont droit à une valeur d'erreur / epsilon tant qu'elle est inférieure à la moitié d'une unité à la dernière place, et le résultat doit seulement être inférieur à la moitié d'une unité dans la dernière lieu pour une opération. Cela explique pourquoi, en cas d'opérations répétées, les erreurs s'additionnent. Pour la double précision IEEE-754, il s'agit du 54ème bit, puisque 53 bits sont utilisés pour représenter la partie numérique (normalisée), également appelée mantisse, du nombre à virgule flottante (par exemple, 5.3 dans 5.3e5). Les sections suivantes détaillent les causes des erreurs matérielles sur diverses opérations en virgule flottante.

3. Cause de l'erreur d'arrondi dans la division

La cause principale de l'erreur dans la division en virgule flottante est les algorithmes de division utilisés pour calculer le quotient. La plupart des systèmes informatiques calculent la division en utilisant la multiplication par un inverse, principalement en Z=X/Y, Z = X * (1/Y). Une division est calculée de manière itérative, c'est-à-dire que chaque cycle calcule certains bits du quotient jusqu'à ce que la précision désirée soit atteinte, ce qui pour IEEE-754 est quelque chose avec une erreur inférieure à une unité à la dernière place. La table des inverses de Y (1 / Y) est connue comme la table de sélection de quotient (QST) dans la division lente, et la taille en bits de la table de sélection de quotient est habituellement la largeur de la base, ou un nombre de bits de le quotient calculé à chaque itération, plus quelques bits de garde. Pour la norme IEEE-754, double précision (64 bits), ce serait la taille de la base du diviseur, plus quelques bits de garde k, où k>=2. Ainsi, par exemple, une table de sélection de quotient typique pour un diviseur qui calcule 2 bits du quotient à la fois (base 4) serait 2+2= 4 bits (plus quelques bits optionnels).

3.1 Erreur d'arrondi de division: Approximation de réciproque

Les réciproques dans le tableau de sélection de quotient dépendent du méthode de division: division lente telle que la division SRT, ou division rapide telle que la division Goldschmidt; chaque entrée est modifiée en fonction de l'algorithme de division afin d'obtenir l'erreur la plus faible possible. En tout cas, cependant, toutes les réciproques sont approximations de la réciproque réelle et introduire un élément d'erreur. Les méthodes de division lente et de division rapide calculent le quotient de manière itérative, c'est-à-dire qu'un certain nombre de bits du quotient sont calculés à chaque étape, puis le résultat est soustrait du dividende et le diviseur répète les étapes jusqu'à ce que l'erreur soit inférieure à unité à la dernière place. Les méthodes de division lente calculent un nombre fixe de chiffres du quotient dans chaque étape et sont généralement moins coûteuses à construire, et les méthodes de division rapide calculent un nombre variable de chiffres par étape et sont généralement plus coûteuses à construire. La partie la plus importante des méthodes de division est que la plupart d'entre elles reposent sur une multiplication répétée par un approximation d'un réciproque, de sorte qu'ils sont enclins à l'erreur.

4. Erreurs d'arrondi dans d'autres opérations: Troncation

Une autre cause des erreurs d'arrondi dans toutes les opérations sont les différents modes de troncature de la réponse finale que permet IEEE-754. Il y a tronqué, rond-vers-zéro, arrondi au plus proche (par défaut), arrondi vers le bas et arrondi. Toutes les méthodes introduisent un élément d'erreur de moins d'une unité à la dernière place pour une seule opération. Au fil du temps et des opérations répétées, la troncature ajoute cumulativement à l'erreur résultante. Cette erreur de troncature est particulièrement problématique dans l'exponentiation, qui implique une forme de multiplication répétée.

5. Opérations répétées

Étant donné que le matériel qui effectue les calculs à virgule flottante ne doit produire qu'un résultat avec une erreur inférieure à la moitié d'une unité à la dernière place pour une seule opération, l'erreur augmentera sur les opérations répétées si elle n'est pas surveillée. C'est la raison pour laquelle dans les calculs qui nécessitent une erreur bornée, les mathématiciens utilisent des méthodes telles que l'utilisation de l'arrondi au plus proche même chiffre à la dernière place de IEEE-754, parce que, au fil du temps, les erreurs sont plus susceptibles de s'annuler, et Arithmétique d'intervalle combiné avec des variations de la IEEE 754 modes d'arrondi pour prévoir les erreurs d'arrondi et les corriger. En raison de sa faible erreur relative par rapport aux autres modes d'arrondi, arrondi au chiffre pair le plus proche (à la dernière place), est le mode d'arrondi par défaut de IEEE-754.

Notez que le mode d'arrondi par défaut, arrondi au plus proche même chiffre à la dernière place, garantit une erreur inférieure à la moitié d'une unité à la dernière place pour une opération. L'utilisation de la troncature, de l'arrondi et de l'arrondi seul peut entraîner une erreur supérieure à la moitié d'une unité à la dernière place, mais inférieure à une unité à la dernière place, ces modes ne sont donc pas recommandés à moins qu'ils soient utilisé dans l'arithmétique par intervalles.

6. Résumé

En bref, la raison fondamentale pour les erreurs dans les opérations à virgule flottante est une combinaison de la troncature dans le matériel, et la troncature d'un réciproque dans le cas de la division. Comme la norme IEEE-754 ne requiert qu'une erreur inférieure à la moitié d'une unité à la dernière place pour une seule opération, les erreurs de virgule flottante sur les opérations répétées s'additionneront à moins d'être corrigées.


490
2018-02-25 21:43



Lorsque vous convertissez .1 ou 1/10 en base 2 (binaire) vous obtenez un motif répétitif après le point décimal, tout comme essayer de représenter 1/3 en base 10. La valeur n'est pas exacte, et donc vous ne pouvez pas faire calcul exact avec les méthodes normales de virgule flottante.


356
2017-11-20 02:39



La plupart des réponses abordent cette question en termes techniques très secs. Je voudrais aborder cela en termes que les êtres humains normaux peuvent comprendre.

Imaginez que vous essayez de découper des pizzas. Vous avez un coupe-pizza robotisé qui peut couper des tranches de pizza exactement à moitié. Il peut réduire de moitié une pizza entière, ou il peut réduire de moitié une tranche existante, mais dans tous les cas, la moitié est toujours exacte.

Ce couteau à pizza a des mouvements très fins, et si vous commencez avec une pizza entière, puis divisez par deux, et continuez à couper la plus petite tranche à chaque fois, vous pouvez faire la moitié 53 fois avant que la tranche est trop petite pour même ses capacités de haute précision. À ce stade, vous ne pouvez plus diviser par deux cette tranche très fine, mais vous devez l'inclure ou l'exclure telle quelle.

Maintenant, comment composeriez-vous toutes les tranches d'une manière qui ajouterait jusqu'à un dixième (0,1) ou un cinquième (0,2) d'une pizza? Pensez-y vraiment, et essayez de travailler dessus. Vous pouvez même essayer d'utiliser une vraie pizza, si vous avez un coupe-pizza de précision mythique à portée de main. :-)


Les programmeurs les plus expérimentés, bien sûr, connaissent la vraie réponse, à savoir qu'il est impossible de exact dixième ou cinquième de la pizza en utilisant ces tranches, peu importe comment finement vous les trancher. Vous pouvez faire une assez bonne approximation, et si vous additionnez l'approximation de 0.1 avec l'approximation de 0.2, vous obtiendrez une assez bonne approximation de 0.3, mais c'est juste une approximation.

Pour les nombres à double précision (qui est la précision qui vous permet de diviser par deux votre pizza 53 fois), les nombres immédiatement inférieurs et supérieurs à 0,1 sont 0,09999999999999999167332731531132594682276248931884765625 et 0,1000000000000000055511151231257827021181583404541015625. Ce dernier est un peu plus proche de 0,1 que le premier, de sorte qu'un analyseur numérique, à partir d'un facteur de 0,1, favorisera ce dernier.

(La différence entre ces deux nombres est la "plus petite tranche" que nous devons décider soit d'inclure, soit d'introduire un biais à la hausse, soit d'exclure, ce qui introduit un biais à la baisse. ulp.)

Dans le cas de 0.2, les chiffres sont tous les mêmes, juste une augmentation d'un facteur 2. Encore une fois, nous privilégions la valeur légèrement supérieure à 0,2.

Notez que dans les deux cas, les approximations pour 0.1 et 0.2 ont un léger biais vers le haut. Si nous ajoutons suffisamment de ces biais, ils pousseront le nombre de plus en plus loin de ce que nous voulons, et en fait, dans le cas de 0,1 + 0,2, le biais est suffisamment élevé pour que le nombre résultant ne soit plus le nombre le plus proche à 0,3.

En particulier, 0,1 + 0,2 est vraiment 0,1000000000000000055511151231257827021181583404541015625 + 0,200000000000000011102230246251565404236316680908203125 = 0,3000000000000000444089209850062616169452667236328125, alors que le nombre le plus proche de 0,3 est en fait 0,299999999999999988897769753748434595763683319091796875.


P.S. Certains langages de programmation fournissent également des pinces à pizza qui peuvent diviser les tranches en dixièmes. Bien que de telles coupeuses de pizza soient rares, si vous en avez accès, vous devriez l'utiliser quand il est important de pouvoir obtenir exactement le dixième ou le cinquième d'une tranche.

(Publié à l'origine sur Quora.)


225
2018-02-25 21:41



Erreurs d'arrondi de virgule flottante. 0.1 ne peut pas être représenté aussi précisément en base-2 qu'en base-10 en raison du facteur premier manquant de 5. De même que 1/3 prend un nombre infini de chiffres pour représenter en décimal, mais est "0.1" en base-3, 0.1 prend un nombre infini de chiffres en base-2 où il ne l'est pas en base-10. Et les ordinateurs n'ont pas une quantité infinie de mémoire.


199
2018-04-09 12:25



En plus des autres réponses correctes, vous pouvez envisager de mettre à l'échelle vos valeurs pour éviter les problèmes avec l'arithmétique en virgule flottante.

Par exemple:

var result = 1.0 + 2.0;     // result === 3.0 returns true

... au lieu de:

var result = 0.1 + 0.2;     // result === 0.3 returns false

L'expression 0.1 + 0.2 === 0.3 résultats false en JavaScript, mais heureusement, l'arithmétique entière en virgule flottante est exacte, donc les erreurs de représentation décimale peuvent être évitées par la mise à l'échelle.

À titre d'exemple pratique, pour éviter les problèmes à virgule flottante où la précision est primordiale, il est recommandé1 gérer l'argent comme un nombre entier représentant le nombre de cents: 2550 cents au lieu de 25.50 dollars.


1 Douglas Crockford: JavaScript: Les bonnes parties: Annexe A - Pièces abominables (page 105).


98
2018-02-23 17:15



Ma réponse est assez longue, alors je l'ai divisé en trois sections. Puisque la question concerne les mathématiques à virgule flottante, j'ai mis l'accent sur ce que la machine fait réellement. Je l'ai également rendu spécifique à la précision double (64 bits), mais l'argument s'applique également à toute arithmétique en virgule flottante.

Préambule

Un Format à virgule flottante binaire double précision IEEE 754 (binary64) nombre représente un nombre de la forme

valeur = (-1) ^ s * (1.m51m50... m2m1m0)2 * 2e-1023

en 64 bits:

  • Le premier bit est le bit de signe: 1 si le nombre est négatif, 0 autrement1.
  • Les 11 bits suivants sont les exposant, lequel est décalage par 1023. En d'autres termes, après avoir lu les bits de l'exposant à partir d'un nombre à double précision, 1023 doit être soustraite pour obtenir la puissance de deux.
  • Les 52 bits restants sont les significand (ou mantisse). Dans la mantisse, un «implicite» 1. est toujours2 omis puisque le bit le plus significatif de toute valeur binaire est 1.

1 - IEEE 754 permet le concept d'un zéro signé - +0 et -0 sont traités différemment: 1 / (+0) est l'infini positif; 1 / (-0) est l'infini négatif. Pour les valeurs nulles, les bits mantisse et exposant sont tous nuls. Note: les valeurs nulles (+0 et -0) ne sont pas explicitement classées comme dénormales2.

2 - Ce n'est pas le cas pour nombres dénormaux, qui ont un exposant offset de zéro (et un implicite 0.). La gamme des nombres dénormaux de double précision est dmin ≤ | x | ≤ dmax, où dmin (le plus petit nombre non nul représentable) est 2-1023 - 51 (≈ 4,94 * 10-324) et dmax (le plus grand nombre dénormal, pour lequel la mantisse consiste entièrement de 1s) est 2-1023 + 1 - 2-1023 - 51 (≈ 2.225 * 10-308).


Transformer un nombre double précision en binaire

De nombreux convertisseurs en ligne existent pour convertir un nombre à virgule flottante double précision en binaire (par exemple, binaryconvert.com), mais voici un exemple de code C # pour obtenir la représentation IEEE 754 pour un nombre double précision (je sépare les trois parties avec des deux-points (:):

public static string BinaryRepresentation(double value)
{
    long valueInLongType = BitConverter.DoubleToInt64Bits(value);
    string bits = Convert.ToString(valueInLongType, 2);
    string leadingZeros = new string('0', 64 - bits.Length);
    string binaryRepresentation = leadingZeros + bits;

    string sign = binaryRepresentation[0].ToString();
    string exponent = binaryRepresentation.Substring(1, 11);
    string mantissa = binaryRepresentation.Substring(12);

    return string.Format("{0}:{1}:{2}", sign, exponent, mantissa);
}

Aller au point: la question originale

(Passer en bas pour la version TL; DR)

Cato Johnston (l'auteur de la question) a demandé pourquoi 0,1 + 0,2! = 0,3.

Ecrit en binaire (avec des deux-points séparant les trois parties), les représentations IEEE 754 des valeurs sont:

0.1 => 0:01111111011:1001100110011001100110011001100110011001100110011010
0.2 => 0:01111111100:1001100110011001100110011001100110011001100110011010

Notez que la mantisse est composée de chiffres récurrents de 0011. C'est clé pourquoi il y a une erreur dans les calculs - 0.1, 0.2 et 0.3 ne peuvent pas être représentés en binaire précisément dans un fini nombre de bits binaires plus de 1/9, 1/3 ou 1/7 peut être représenté précisément dans chiffres décimaux.

Conversion des exposants en décimales, suppression de l'offset et rajout de l'implicite 1 (entre crochets), 0,1 et 0,2 sont:

0.1 = 2^-4 * [1].1001100110011001100110011001100110011001100110011010
0.2 = 2^-3 * [1].1001100110011001100110011001100110011001100110011010

Pour ajouter deux nombres, l'exposant doit être le même, à savoir:

0.1 = 2^-3 *  0.1100110011001100110011001100110011001100110011001101(0)
0.2 = 2^-3 *  1.1001100110011001100110011001100110011001100110011010
sum = 2^-3 * 10.0110011001100110011001100110011001100110011001100111

Puisque la somme n'est pas de la forme 2n * 1. {bbb} on augmente l'exposant de un et décale la décimale (binaire) point pour obtenir:

sum = 2^-2 * 1.0011001100110011001100110011001100110011001100110011(1)

Il y a maintenant 53 bits dans la mantisse (le 53ème est entre crochets dans la ligne ci-dessus). Le défaut mode d'arrondi pour IEEE 754 est 'Arrondir au plus proche'- c'est-à-dire si un nombre X tombe entre deux valeurs une et b, la valeur où le bit le moins significatif est zéro est choisie.

a = 2^-2 * 1.0011001100110011001100110011001100110011001100110011
x = 2^-2 * 1.0011001100110011001100110011001100110011001100110011(1)
b = 2^-2 * 1.0011001100110011001100110011001100110011001100110100

Notez que une et b ne diffèrent que dans le dernier bit; ...0011 + 1 = ...0100. Dans ce cas, la valeur avec le bit le moins significatif de zéro est b, donc la somme est:

sum = 2^-2 * 1.0011001100110011001100110011001100110011001100110100

TL; DR

L'écriture 0.1 + 0.2 dans une représentation binaire IEEE 754 (avec les deux points séparant les trois parties) et en le comparant à 0.3, c'est (j'ai mis les bits distincts entre crochets):

0.1 + 0.2 => 0:01111111101:0011001100110011001100110011001100110011001100110[100]
0.3       => 0:01111111101:0011001100110011001100110011001100110011001100110[011]

Convertis en décimal, ces valeurs sont:

0.1 + 0.2 => 0.300000000000000044408920985006...
0.3       => 0.299999999999999988897769753748...

La différence est exactement 2-54, qui est ~ 5.5511151231258 × 10-17 - insignifiant (pour de nombreuses applications) par rapport aux valeurs d'origine.

Comparer les derniers bits d'un nombre à virgule flottante est intrinsèquement dangereux, comme tous ceux qui lisent le fameux "Ce que tout informaticien devrait savoir sur l'arithmétique en virgule flottante"(qui couvre toutes les parties principales de cette réponse) saura.

La plupart des calculatrices utilisent d'autres chiffres de garde pour contourner ce problème, qui est comment 0.1 + 0.2 donnerait 0.3: les derniers bits sont arrondis.


80
2018-03-16 05:27



Les nombres à virgule flottante stockés dans l'ordinateur sont constitués de deux parties, un nombre entier et un exposant auquel la base est portée et multipliée par la partie entière.

Si l'ordinateur travaillait en base 10, 0.1 serait 1 x 10⁻¹, 0.2 serait 2 x 10⁻¹, et 0.3 serait 3 x 10⁻¹. Les nombres entiers sont faciles et précis, ce qui ajoute 0.1 + 0.2 va évidemment entraîner 0.3.

Les ordinateurs ne fonctionnent généralement pas en base 10, ils fonctionnent en base 2. Vous pouvez toujours obtenir des résultats exacts pour certaines valeurs, par exemple 0.5 est 1 x 2⁻¹ et 0.25 est 1 x 2⁻²et en ajoutant les résultats dans 3 x 2⁻², ou 0.75. Exactement.

Le problème vient avec des nombres qui peuvent être représentés exactement dans la base 10, mais pas dans la base 2. Ces nombres doivent être arrondis à leur équivalent le plus proche. En supposant le très courant format de virgule flottante IEEE 64 bits, le nombre le plus proche de 0.1 est 3602879701896397 x 2⁻⁵⁵, et le nombre le plus proche de 0.2 est 7205759403792794 x 2⁻⁵⁵; les ajouter ensemble résulte en 10808639105689191 x 2⁻⁵⁵ou une valeur décimale exacte de 0.3000000000000000444089209850062616169452667236328125. Les nombres à virgule flottante sont généralement arrondis pour l'affichage.


48
2018-02-25 21:42