Pourquoi les nombres à virgule flottante sont-ils inexacts?

198

Pourquoi certains nombres perdent leur précision lorsqu'ils sont stockés sous forme de nombres à virgule flottante?

Par exemple, le nombre décimal 9.2peut être exprimé exactement comme un rapport de deux nombres décimaux ( 92/10), qui peuvent tous deux être exprimés exactement en binaire ( 0b1011100/0b1010). Cependant, le même rapport stocké sous forme de nombre à virgule flottante n'est jamais exactement égal à 9.2:

32-bit "single precision" float: 9.19999980926513671875
64-bit "double precision" float: 9.199999999999999289457264239899814128875732421875

Comment un nombre aussi simple en apparence peut-il être "trop ​​grand" pour être exprimé sur 64 bits de mémoire?

mhlester
la source

Réponses:

241

Dans la plupart des langages de programmation, les nombres à virgule flottante sont représentés un peu comme la notation scientifique : avec un exposant et une mantisse (également appelée significande). Un nombre très simple, disons 9.2, est en fait cette fraction:

5179139571476070 * 2 -49

Où se trouve l'exposant -49et la mantisse 5179139571476070. La raison pour laquelle il est impossible de représenter certains nombres décimaux de cette façon est que l'exposant et la mantisse doivent être des nombres entiers. En d'autres termes, tous les flottants doivent être un entier multiplié par un puissance entière de 2 .

9.2peut être simplement 92/10, mais 10 ne peut pas être exprimé comme 2 n si n est limité à des valeurs entières.


Voir les données

Tout d'abord, quelques fonctions pour voir les composants qui font un 32 et 64 bits float. Brossez-les si vous ne vous souciez que de la sortie (exemple en Python):

def float_to_bin_parts(number, bits=64):
    if bits == 32:          # single precision
        int_pack      = 'I'
        float_pack    = 'f'
        exponent_bits = 8
        mantissa_bits = 23
        exponent_bias = 127
    elif bits == 64:        # double precision. all python floats are this
        int_pack      = 'Q'
        float_pack    = 'd'
        exponent_bits = 11
        mantissa_bits = 52
        exponent_bias = 1023
    else:
        raise ValueError, 'bits argument must be 32 or 64'
    bin_iter = iter(bin(struct.unpack(int_pack, struct.pack(float_pack, number))[0])[2:].rjust(bits, '0'))
    return [''.join(islice(bin_iter, x)) for x in (1, exponent_bits, mantissa_bits)]

Il y a beaucoup de complexité derrière cette fonction, et ce serait assez tangent à expliquer, mais si vous êtes intéressé, la ressource importante pour nos besoins est la module struct .

Python floatest un nombre 64 bits à double précision. Dans d'autres langages tels que C, C ++, Java et C #, la double précision a un type distinctdouble , qui est souvent implémenté en 64 bits.

Lorsque nous appelons cette fonction avec notre exemple 9.2, voici ce que nous obtenons:

>>> float_to_bin_parts(9.2)
['0', '10000000010', '0010011001100110011001100110011001100110011001100110']

Interprétation des données

Vous verrez que j'ai divisé la valeur de retour en trois composants. Ces composants sont:

  • Signe
  • Exposant
  • Mantissa (également appelée Significand ou Fraction)

Signe

Le signe est stocké dans le premier composant en tant que bit unique. C'est facile à expliquer: 0signifie que le flotteur est un nombre positif; 1signifie que c'est négatif. Parce que 9.2c'est positif, notre valeur de signe est0 .

Exposant

L'exposant est stocké dans le composant central sous forme de 11 bits. Dans notre cas 0b10000000010,. En décimal, cela représente la valeur 1026. Une particularité de ce composant est que vous devez soustraire un nombre égal à 2 (# de bits) - 1 - 1 pour obtenir le véritable exposant; dans notre cas, cela signifie soustraire 0b1111111111(nombre décimal 1023) pour obtenir le véritable exposant,0b00000000011 (nombre décimal 3).

Mantissa

La mantisse est stockée dans le troisième composant sous 52 bits. Cependant, il y a aussi une bizarrerie à ce composant. Pour comprendre cette bizarrerie, considérez un nombre en notation scientifique, comme ceci:

6.0221413x10 23

La mantisse serait la 6.0221413. Rappelons que la mantisse en notation scientifique commence toujours par un seul chiffre non nul. Il en va de même pour le binaire, sauf que le binaire n'a que deux chiffres: 0et 1. La mantisse binaire commence donc toujours par 1! Lorsqu'un flottant est stocké, le 1devant de la mantisse binaire est omis pour économiser de l'espace; nous devons le replacer à l'avant de notre troisième élément pour obtenir la vraie mantisse:

1.0010011001100110011001100110011001100110011001100110

Cela implique plus qu'un simple ajout, car les bits stockés dans notre troisième composant représentent en fait la partie fractionnaire de la mantisse, à droite du point radix .

Lorsque nous traitons des nombres décimaux, nous "déplaçons le point décimal" en multipliant ou en divisant par des puissances de 10. En binaire, nous pouvons faire la même chose en multipliant ou en divisant par des puissances de 2. Puisque notre troisième élément a 52 bits, nous divisons par 2 52 pour le déplacer 52 places vers la droite:

0,0010011001100110011001100110011001100110011001100110

En notation décimale, cela revient à diviser 675539944105574par 4503599627370496pour obtenir 0.1499999999999999. (Ceci est un exemple d'un rapport qui peut être exprimé exactement en binaire, mais seulement approximativement en décimal; pour plus de détails, voir: 675539944105574/4503599627370496 .)

Maintenant que nous avons transformé le troisième composant en nombre fractionnaire, l'ajout 1donne la vraie mantisse.

Récapitulation des composants

  • Signe (premier composant): 0pour positif, 1pour négatif
  • Exposant (composante centrale): Soustraire 2 (# de bits) - 1-1 pour obtenir le véritable exposant
  • Mantisse (dernier composant): divisez par 2 (# de bits) et ajoutez 1pour obtenir la vraie mantisse

Calcul du nombre

En réunissant les trois parties ensemble, on nous donne ce numéro binaire:

1,0010011001100110011001100110011001100110011001100110 x 10 11

Que nous pouvons ensuite convertir du binaire en décimal:

1,149999999999999999 x 2 3 (inexact!)

Et multipliez pour révéler la représentation finale du nombre que nous avons commencé avec ( 9.2) après avoir été stocké en tant que valeur à virgule flottante:

9.1999999999999993


Représenter comme une fraction

9.2

Maintenant que nous avons construit le nombre, il est possible de le reconstruire en une fraction simple:

1,0010011001100110011001100110011001100110011001100110 x 10 11

Décalez la mantisse en un nombre entier:

10010011001100110011001100110011001100110011001100110 x 10 11-110100

Convertir en décimal:

5179139571476070 x 2 3-52

Soustrayez l'exposant:

5179139571476070 x 2 -49

Transformez l'exposant négatif en division:

5179139571476070/2 49

Exposant multiplié:

5179139571476070/562949953421312

Ce qui équivaut à:

9.1999999999999993

9.5

>>> float_to_bin_parts(9.5)
['0', '10000000010', '0011000000000000000000000000000000000000000000000000']

Déjà, vous pouvez voir que la mantisse n'est que de 4 chiffres, suivie de beaucoup de zéros. Mais passons à travers les allures.

Assemblez la notation scientifique binaire:

1,0011 x 10 11

Décalez le point décimal:

10011 x 10 11-100

Soustrayez l'exposant:

10011 x 10 -1

Binaire à décimal:

19 x 2 -1

Exposant négatif de la division:

19/2 1

Exposant multiplié:

19/2

Équivaut à:

9.5



Lectures complémentaires

mhlester
la source
1
Il y a aussi un joli tutoriel qui montre comment aller dans l'autre sens - étant donné une représentation décimale d'un nombre, comment construire l'équivalent en virgule flottante. L'approche de «division longue» montre très clairement comment vous vous retrouvez avec un «reste» après avoir essayé de représenter le nombre. Doit être ajouté si vous voulez être vraiment "canonique" avec votre réponse.
Floris
1
Si vous parlez de Python et de virgule flottante, je suggère au moins d'inclure le didacticiel Python dans vos liens: docs.python.org/3.4/tutorial/floatingpoint.html C'est censé être le guichet unique ressource pour les problèmes de virgule flottante pour les programmeurs Python. Si cela fait défaut d'une certaine manière (et c'est presque sûrement le cas), veuillez ouvrir un problème sur le suivi des bogues Python pour les mises à jour ou les modifications.
Mark Dickinson
@mhlester Si cela se transforme en wiki communautaire, n'hésitez pas à incorporer ma réponse dans la vôtre.
Nicu Stiurca
5
Cette réponse devrait également être liée à floating-point-gui.de , car c'est probablement la meilleure introduction pour les débutants. OMI, il devrait même aller au-delà de "ce que tout informaticien devrait savoir ..." - de nos jours, les gens qui peuvent raisonnablement comprendre le document de Goldberg en sont déjà bien conscients.
Daniel Pryden
1
"Ceci est un exemple d'un rapport qui peut être exprimé exactement en binaire, mais seulement approximativement en décimal". Ce n'est pas vrai. Tous ces ratios «nombre sur une puissance de deux» sont exacts en décimal. Toute approximation sert uniquement à raccourcir le nombre décimal - pour plus de commodité.
Rick Regan
29

Ce n'est pas une réponse complète ( mhlester déjà couvert beaucoup de bonnes choses que je ne reproduirai pas), mais je voudrais souligner à quel point la représentation d'un nombre dépend de la base dans laquelle vous travaillez.

Considérez la fraction 2/3

Dans la bonne base 10, nous l'écrivons généralement comme quelque chose comme

  • 0,666 ...
  • 0,666
  • 0,667

Lorsque nous regardons ces représentations, nous avons tendance à associer chacune d'entre elles à la fraction 2/3, même si seule la première représentation est mathématiquement égale à la fraction. Les deuxième et troisième représentations / approximations ont une erreur de l'ordre de 0,001, ce qui est en réalité bien pire que l'erreur entre 9,2 et 9,1999999999999993. En fait, la deuxième représentation n'est même pas arrondie correctement! Néanmoins, nous n'avons pas de problème avec 0.666 comme approximation du nombre 2/3, donc nous ne devrions pas vraiment avoir de problème avec la façon dont 9.2 est approximé dans la plupart des programmes . (Oui, dans certains programmes, cela compte.)

Bases numériques

Voici donc où les bases numériques sont cruciales. Si nous essayions de représenter 2/3 en base 3, alors

(2/3) 10 = 0,2 3

En d'autres termes, nous avons une représentation exacte et finie pour le même nombre en changeant de base! Le point à retenir est que même si vous pouvez convertir n'importe quel nombre en n'importe quelle base, tous les nombres rationnels ont des représentations finies exactes dans certaines bases mais pas dans d'autres .

Pour ramener ce point à la maison, regardons 1/2. Cela pourrait vous surprendre que même si ce nombre parfaitement simple a une représentation exacte en base 10 et 2, il nécessite une représentation répétée en base 3.

(1/2) 10 = 0,5 10 = 0,1 2 = 0,1111 ... 3

Pourquoi les nombres à virgule flottante sont-ils inexacts?

Parce que souvent, ce sont des logiques approximatives qui ne peuvent pas être représentées de manière finie dans la base 2 (les chiffres se répètent), et en général, elles sont des nombres réels (éventuellement irrationnels) qui peuvent ne pas être représentables en nombre fini de chiffres dans n'importe quelle base.

Nicu Stiurca
la source
3
En d'autres termes, la base-3 serait parfaite pour 1/3tout comme la base-10 est parfaite pour 1/10. Aucune fraction ne fonctionne en base-2
mhlester
2
@mhlester Oui. Et en général, la base-N est parfaite pour toute fraction dont le dénominateur est Nou un multiple de celui-ci.
Nicu Stiurca
2
Et c'est une des raisons pour lesquelles certaines boîtes à outils numériques gardent une trace de "ce qui a été divisé par quoi" et, dans le processus, peuvent conserver une "précision infinie" pour tous les nombres rationnels. Tout comme les physiciens aiment garder leurs équations symboliques jusqu'au dernier moment possible, au cas où les facteurs πetc. s'annuleraient.
Floris
3
@Floris J'ai également vu des cas où un algorithme qui n'effectue que l'arithmétique de base (c'est-à-dire qui préserve la rationalité de l'entrée), détermine si l'entrée était (probable) rationnelle, effectue le calcul en utilisant une arithmétique à virgule flottante normale, puis ré-estime une rationnelle approximation à la fin pour corriger les erreurs d'arrondi. En particulier, l' algorithme de forme échelonnée à lignes réduites de Matlab le fait, et il aide énormément la stabilité numérique.
Nicu Stiurca
@SchighSchagh - intéressant, je ne le savais pas. Je sais que la stabilité numérique est quelque chose qui n'est pas suffisamment enseigné en ces jours de double double précision. Ce qui signifie que beaucoup manquent d'apprendre l'élégance de nombreux beaux algorithmes. J'aime beaucoup les algorithmes qui calculent et corrigent leurs propres erreurs.
Floris
13

Bien que toutes les autres réponses soient bonnes, il manque encore une chose:

Il est impossible de représenter des nombres irrationnels (par exemple π, sqrt(2), log(3), etc.) précisément!

Et c'est en fait pourquoi ils sont appelés irrationnels. Aucune quantité de stockage de bits au monde ne suffirait à contenir même l'un d'entre eux. Seulement symbolique arithmétique est capable de conserver leur précision.

Bien que si vous limitez vos besoins en mathématiques à des nombres rationnels, seul le problème de précision devient gérable. Vous auriez besoin de stocker une paire d'entiers (éventuellement très grands) aet bde conserver le nombre représenté par la fraction a/b. Toute votre arithmétique devrait être effectuée sur des fractions comme dans les mathématiques du secondaire (par exemple a/b * c/d = ac/bd).

Mais bien sûr vous encore courir dans le même genre de problème quand pi, sqrt, log,sin , etc. sont impliqués.

TL; DR

Pour l'arithmétique accélérée matériellement, seule une quantité limitée de nombres rationnels peut être représentée. Chaque nombre non représentable est approximatif. Certains nombres (c'est-à-dire irrationnels) ne peuvent jamais être représentés quel que soit le système.

LumpN
la source
4
Fait intéressant, des bases irrationnelles existent. Phinaire , par exemple.
Veedrac
5
les nombres irrationnels peuvent être (uniquement) représentés dans leur base. Par exemple pi vaut 10 en base pi
phuclv
4
Le point reste valable: certains nombres ne peuvent jamais être représentés quel que soit le système. Vous ne gagnez rien en changeant votre base car certains autres numéros ne peuvent plus être représentés.
LumpN
4

Il existe une infinité de nombres réels (si nombreux que vous ne pouvez pas les énumérer) et il existe une infinité de nombres rationnels (il est possible de les énumérer).

La représentation en virgule flottante est une représentation finie (comme n'importe quoi dans un ordinateur), donc inévitablement de nombreux nombres sont impossibles à représenter. En particulier, 64 bits ne vous permettent de distinguer que 18.446.744.073.709.551.616 valeurs différentes (ce qui n'est rien comparé à l'infini). Avec la convention standard, 9.2 n'en fait pas partie. Ceux qui peuvent être de la forme m.2 ^ e pour certains entiers m et e.


Vous pourriez trouver un système de numérotation différent, basé sur 10 par exemple, où 9.2 aurait une représentation exacte. Mais d'autres chiffres, disons 1/3, seraient toujours impossibles à représenter.


Notez également que les nombres à virgule flottante double précision sont extrêmement précis. Ils peuvent représenter n'importe quel nombre dans une très large plage avec jusqu'à 15 chiffres exacts. Pour les calculs de la vie quotidienne, 4 ou 5 chiffres sont plus que suffisants. Vous n'aurez jamais vraiment besoin de ces 15, sauf si vous voulez compter chaque milliseconde de votre vie.

Yves Daoust
la source
1

Pourquoi ne pouvons-nous pas représenter 9.2 en virgule flottante binaire?

Les nombres à virgule flottante sont (simplifiant légèrement) un système de numérotation positionnelle avec un nombre restreint de chiffres et un point radix mobile.

Une fraction ne peut être exprimée exactement en utilisant un nombre fini de chiffres dans un système de numérotation positionnelle que si les facteurs premiers du dénominateur (lorsque la fraction est exprimée en termes les plus bas) sont des facteurs de la base.

Les facteurs premiers de 10 sont 5 et 2, donc en base 10, nous pouvons représenter n'importe quelle fraction de la forme a / (2 b 5 c ).

Par contre le seul facteur premier de 2 est 2, donc en base 2 on ne peut représenter que des fractions de la forme a / (2 b )

Pourquoi les ordinateurs utilisent-ils cette représentation?

Parce que c'est un format simple à utiliser et qu'il est suffisamment précis pour la plupart des utilisations. Fondamentalement, c'est la même raison pour laquelle les scientifiques utilisent la «notation scientifique» et arrondissent leurs résultats à un nombre raisonnable de chiffres à chaque étape.

Il serait certainement possible de définir un format de fraction, avec (par exemple) un numérateur 32 bits et un dénominateur 32 bits. Il pourrait représenter des nombres que la virgule flottante double précision IEEE ne pourrait pas, mais il y aurait également de nombreux nombres pouvant être représentés en virgule flottante double précision qui ne pourraient pas être représentés dans un format de fraction de taille fixe.

Cependant, le gros problème est qu'un tel format est difficile à faire des calculs. Pour deux raisons.

  1. Si vous voulez avoir exactement une représentation de chaque nombre, après chaque calcul, vous devez réduire la fraction à ses termes les plus bas. Cela signifie que pour chaque opération, vous devez essentiellement effectuer le plus grand calcul de diviseur commun.
  2. Si après votre calcul vous vous retrouvez avec un résultat non représentable parce que le numérateur ou le dénominateur vous devez trouver le résultat représentable le plus proche. Ce n'est pas anodin.

Certaines langues proposent des types de fraction, mais généralement elles le font en combinaison avec une précision arbitraire, cela évite d'avoir à se soucier de l'approximation des fractions mais cela crée son propre problème, lorsqu'un nombre passe par un grand nombre d'étapes de calcul de la taille du dénominateur et d'où le stockage nécessaire à la fraction peut exploser.

Certaines langues proposent également des types décimaux à virgule flottante, ceux-ci sont principalement utilisés dans des scénarios où il est important que les résultats que l'ordinateur obtient correspondent aux règles d'arrondi préexistantes écrites en pensant aux humains (principalement les calculs financiers). Celles-ci sont légèrement plus difficiles à travailler que les virgules flottantes binaires, mais le plus gros problème est que la plupart des ordinateurs ne les prennent pas en charge.

plugwash
la source
-4

Essaye ça

DecimalFormat decimalFormat = new DecimalFormat("#.##");
String.valueOf(decimalFormat.format(decimalValue))));

' decimalValue' est votre valeur à convertir.

Popal
la source